MHB Find the general formula of the recurrence relation

AI Thread Summary
The discussion revolves around finding the general formula for the recurrence relation defined by \( a_k = 3^k - a_{k-1} \) with \( a_0 = 1 \). Participants explore various transformations of the sequence, ultimately arriving at the expression \( a_k = \frac{(-1)^k + 3^{k+1}}{4} \) through methods such as induction and the characteristic root approach. They clarify the importance of initial conditions and the role of even and odd indices in deriving a unified formula. The conversation emphasizes the use of geometric series to express the terms succinctly. The final consensus confirms the derived formula aligns with previous findings in the thread.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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:
 
Physics news on Phys.org
evinda said:
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)

evinda said:
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? 🤔

evinda said:
Also, why is the latter equal to $(-1)^k (3^k+3^{k-1}+\dots+1)$ ?
It isn't. (Shake)
 
I would look at the characteristic root and from that observe the homogeneous solution is:

$$h_k=c_1(-1)^k$$

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

$$p_k=A3^k+B$$

Substitution into the recurrence yields:

$$A3^k+B+A3^{k-1}+B=3^k$$

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

'$$A=\frac{3}{4},\,B=0$$

And so the general solution is:

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

We are told:

$$a_0=c_1+\frac{3}{4}=1\implies c_1=\frac{1}{4}$$

Hence:

$$a_k=\frac{(-1)^k+3^{k+1}}{4}$$
 
Klaas van Aarsen said:
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)

Klaas van Aarsen said:
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:
Klaas van Aarsen said:
It isn't. (Shake)

Ok... :unsure::unsure::unsure: So after getting the expression for $a_k$, we will discuss it (Wasntme)(Blush)
 
evinda said:
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? 🤔

evinda said:
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$$
? 🤔
 
Klaas van Aarsen said:
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)

Klaas van Aarsen said:
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)
 
evinda said:
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$. 🤔
 
Klaas van Aarsen said:
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:
 
evinda said:
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? 🤔
 
  • #10
Klaas van Aarsen said:
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:
 
  • #11
evinda said:
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$$
? 🤔
 
  • #12
Klaas van Aarsen said:
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? :)
 
  • #13
evinda said:
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)
 
  • #14
Oh yes, right! Thank you both! (Blush)
 
Back
Top