Welcome to our community

Be a part of something great, join today!

Find the general formula of the recurrence relation

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hello!!! (Wave)

Suppose that we have the recurrence relation $a_k=3^k-a_{k-1}, a_0=1$.

By replacing the terms of the sequence we get that it is equal to $a_k=3^k-3^{k+1}+3^{k+2}-a_{k-3}$.

How do we get that it is equal to $a_k=3^{k}-3^{k-1}+3^{k-2}- \dots+ (-1)^k$ ? :unsure:

Also, why is the latter equal to $(-1)^k (3^k+3^{k-1}+\dots+1)$ ? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
Suppose that we have the recurrence relation $a_k=3^k-a_{k-1}, a_0=1$.

By replacing the terms of the sequence we get that it is equal to $a_k=3^k-3^{k+1}+3^{k+2}-a_{k-3}$.
Hey evinda !!

Shouldn't that be $a_k=3^k-3^{k\color{red}{-1}}+3^{k\color{red}{-2}}-a_{k-3}$? (Worried)

How do we get that it is equal to $a_k=3^{k}-3^{k-1}+3^{k-2}- \dots+ (-1)^k$ ?
We can 'guess' by seeing the pattern and assuming it extends all the way to $a_0$, which is $1$.
And we can prove it by induction, can't we? 🤔

Also, why is the latter equal to $(-1)^k (3^k+3^{k-1}+\dots+1)$ ?
It isn't. (Shake)
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,734
I would look at the characteristic root and from that observe the homogeneous solution is:

\(\displaystyle h_k=c_1(-1)^k\)

Next, I would use the method of undetermined coefficients to state the particular solution is of the form:

\(\displaystyle p_k=A3^k+B\)

Substitution into the recurrence yields:

\(\displaystyle A3^k+B+A3^{k-1}+B=3^k\)

\(\displaystyle 4A3^{k-1}+2B=3\cdot3^{k-1}+0\)'

'\(\displaystyle A=\frac{3}{4},\,B=0\)

And so the general solution is:

\(\displaystyle a_k=h_k+p_k=c_1(-1)^k+\frac{1}{4}3^{k+1}\)

We are told:

\(\displaystyle a_0=c_1+\frac{3}{4}=1\implies c_1=\frac{1}{4}\)

Hence:

\(\displaystyle a_k=\frac{(-1)^k+3^{k+1}}{4}\)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hey evinda !!

Shouldn't that be $a_k=3^k-3^{k\color{red}{-1}}+3^{k\color{red}{-2}}-a_{k-3}$? (Worried)
Oh yes, right! (Nod)

We can 'guess' by seeing the pattern and assuming it extends all the way to $a_0$, which is $1$.
And we can prove it by induction, can't we? 🤔
At the base case, for $k=1$, $a_1=3-a_0=2$.

$3^1-3^{1-1}+(-1)^1=1$.... These are not equal... Have I done something wrong? o_O

Then assuming that $a_m=3^m-3^{m-1}+3^{m-2}+\dots+ (-1)^m$, we get that

$$a_{m+1}=3^{m+1}-a_m= \dots= 3^m-3^{m-1}- \dots+(-1)^m$$

which again is not the resired result.... I am doing something wrong? :unsure:


It isn't. (Shake)
Ok... :unsure::unsure::unsure: So after getting the expression for $a_k$, we will discuss it (Wasntme)(Blush)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
At the base case, for $k=1$, $a_1=3-a_0=2$.

$3^1-3^{1-1}+(-1)^1=1$.... These are not equal... Have I done something wrong?
The base case for $k=0$ is $a_0=(-1)^0=1$, which is correct, isn't it? 🤔

The case for $k=1$ is $a_1=3^1+(-1)^1=2$.
And we expect $a_1=3^1-a_0=2$, so they match don't they? 🤔

Then assuming that $a_m=3^m-3^{m-1}+3^{m-2}+\dots+ (-1)^m$, we get that

$$a_{m+1}=3^{m+1}-a_m= \dots= 3^m-3^{m-1}- \dots+(-1)^m$$

which again is not the resired result.... I am doing something wrong?
Shouldn't it be:
$$a_{m+1}=3^{m+1}-a_m= \dots= 3^{m\color{red}{+1}}-(3^m-3^{m-1}- \dots+(-1)^m)=3^{m+1}-3^m+3^{m-1}+\ldots-(-1)^m$$
? 🤔
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
The base case for $k=0$ is $a_0=(-1)^0=1$, which is correct, isn't it? 🤔

The case for $k=1$ is $a_1=3^1+(-1)^1=2$.
And we expect $a_1=3^1-a_0=2$, so they match don't they? 🤔
I haven't understood how we check the cases $k=0,1$... :unsure:


For example for $k=0$ why at the formula $a_k=3^k-3^{k-1}+3^{k-2}- \dots +(-1)^k$ don't we take also into consideration the term $3^0$, i.e. why isn't the result $3^0+(-1)^0$ ? o_O Could you explain it to me? (Wasntme)

Shouldn't it be:
$$a_{m+1}=3^{m+1}-a_m= \dots= 3^{m\color{red}{+1}}-(3^m-3^{m-1}- \dots+(-1)^m)=3^{m+1}-3^m+3^{m-1}+\ldots-(-1)^m$$
? 🤔
Oh yes, right!!! (Nod)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
I haven't understood how we check the cases $k=0,1$...

For example for $k=0$ why at the formula $a_k=3^k-3^{k-1}+3^{k-2}- \dots +(-1)^k$ don't we take also into consideration the term $3^0$, i.e. why isn't the result $3^0+(-1)^0$ ? Could you explain it to me?
Consider the case for $k=3$:
$$a_3 = 3^3 - 3^2 + \ldots + (-1)^3$$
Doesn't it make sense that its proper full expression is:
$$a_3 = 3^3 - 3^2 + 3^1 - 3^0$$
? 🤔

If so, then for $k=0$, we only get the zero order term. That is, $a_0=3^0$.
And for $k=1$, we get the first order term together with the zero order term. That is, $a_1=3^1 - 3^0$. 🤔
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Consider the case for $k=3$:
$$a_3 = 3^3 - 3^2 + \ldots + (-1)^3$$
Doesn't it make sense that its proper full expression is:
$$a_3 = 3^3 - 3^2 + 3^1 - 3^0$$
? 🤔

If so, then for $k=0$, we only get the zero order term. That is, $a_0=3^0$.
And for $k=1$, we get the first order term together with the zero order term. That is, $a_1=3^1 - 3^0$. 🤔
I see!!! (Nod) And how can we get from this a general formula for the terms of the sequence? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
I see!!! And how can we get from this a general formula for the terms of the sequence?
It's a geometric sequence isn't it? 🤔
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
It's a geometric sequence isn't it? 🤔
We have that $a_k=\sum_{i=0}^k (-3)^k$ when $k$ is even and $a_k=-\sum_{i=0}^k (-3)^k$ when $k$ is odd, right? :unsure:

If so, can we write also a general equality for $a_k$ that does not depend on whether $k$ is even or odd? :unsure::unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
We have that $a_k=\sum_{i=0}^k (-3)^k$ when $k$ is even and $a_k=-\sum_{i=0}^k (-3)^k$ when $k$ is odd, right?

If so, can we write also a general equality for $a_k$ that does not depend on whether $k$ is even or odd?
Sure.
How about:
$$a_k=(-1)^k\sum_{i=0}^k (-3)^k$$
? 🤔
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Sure.
How about:
$$a_k=(-1)^k\sum_{i=0}^k (-3)^k$$
? 🤔
Using the fact that $\sum_{k=0}^{n-1} (ar^k)=a \left( \frac{1-r^n}{1-r}\right)$, we get that $\sum_{i=0}^k (-3)^i=\frac{1-(-3)^{k+1}}{4}$ and so we deduce that

$$a_k=\frac{(-1)^k+3^{k+1}}{4}.$$

Right? :)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,679
Using the fact that $\sum_{k=0}^{n-1} (ar^k)=a \left( \frac{1-r^n}{1-r}\right)$, we get that $\sum_{i=0}^k (-3)^i=\frac{1-(-3)^{k+1}}{4}$ and so we deduce that

$$a_k=\frac{(-1)^k+3^{k+1}}{4}.$$

Right?
Yep.
And that is what MarkFL already posted. (Nod)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Oh yes, right!!! Thank you both!!! (Blush)