Find the general formula of the recurrence relation

[evinda]

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:

 

[I like Serena]

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]

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]

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?

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)

 

[I like Serena]

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]

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$ ? 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)

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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? :)

 

[I like Serena]

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]

Oh yes, right! Thank you both! (Blush)