# Find the general formula of the recurrence relation

#### evinda

##### Well-known member
MHB Site Helper
Hello!!! 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$ ? Also, why is the latter equal to $(-1)^k (3^k+3^{k-1}+\dots+1)$ ? • Klaas van Aarsen

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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}$? 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. • topsquark and evinda

#### MarkFL

Staff member
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
Hey evinda !!

Shouldn't that be $a_k=3^k-3^{k\color{red}{-1}}+3^{k\color{red}{-2}}-a_{k-3}$? Oh yes, right! 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? 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? It isn't. Ok...   So after getting the expression for $a_k$, we will discuss it  #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

#### evinda

##### Well-known member
MHB Site Helper
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$... 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? 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!!! #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

#### evinda

##### Well-known member
MHB Site Helper
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!!! And how can we get from this a general formula for the terms of the sequence? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

#### evinda

##### Well-known member
MHB Site Helper
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? If so, can we write also a general equality for $a_k$ that does not depend on whether $k$ is even or odd?  #### Klaas van Aarsen

##### MHB Seeker
Staff member
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.
$$a_k=(-1)^k\sum_{i=0}^k (-3)^k$$
? • evinda

#### evinda

##### Well-known member
MHB Site Helper
Sure.
$$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
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. • anemone, MarkFL and evinda

#### evinda

##### Well-known member
MHB Site Helper
Oh yes, right!!! Thank you both!!! • MarkFL and Klaas van Aarsen