# Strong Induction

#### KOO

##### New member
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

Staff member
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
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

Okay as your next step, I would distribute on the right side, keeping in mind that $6=2\cdot3$.