Welcome to our community

Be a part of something great, join today!

Strong Induction

KOO

New member
Oct 19, 2013
19
Let $(x_n)$ be a sequence given by the following recursion formula:

$$x_1 = 3, x_2 = 7,\text{ and }x_{n+1} = 5x_n - 6x_{n-1}$$

Prove that for all $n\in\Bbb N$, $x_n = 2^n + 3^{n-1}$.

Attempt:

For $n = 1$, we have $2^1 + 3^0 = 3 = x_1$ TRUE
For $n = 2$, we have $2^2 + 3^1 = 7 = x_2$ TRUE

Assume $x_k = 2^k + 3^{k-1}$ for some $k\in\Bbb N$.

Now, for $n = k+1$:

$$\begin{align*}
x_{k+1} &= 5x_k - 6x_{k-1}\\
&= 5\left(2^k + 3^{k-1}\right) - 6\left(2^{k-1} + 3^{k-2}\right)
\end{align*}$$

What Next?
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Are you required to use induction, or did you choose to do so, because there is a much simpler way to derive the closed form for the recursion.
 

KOO

New member
Oct 19, 2013
19
Are you required to use induction, or did you choose to do so, because there is a much simpler way to derive the closed form for the recursion.
We are required to use induction.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Okay as your next step, I would distribute on the right side, keeping in mind that $6=2\cdot3$.