I do not know how to solve for Induction Conclusion

Question

A sequence has $x_1=8$, $x_2=32$, $x_{n}= 2x_{n-1}+3x_{n-2}$ for $n \ge 3.$ Prove, for all $i$ of Naturals, $X_i = 2 (-1)^i + 10 \cdot 3^{i-1}$

I got bases covered, and I got the inductive step as $X_{i} = 2 * (-1)^k + 10 * 3^{k-1}$. I do not know how to follow up with k+1, as I get complete gibberish. Any suggestions

Could someone guide me through each step?

My work so far:—

Base Cases include $x = 1, 2.$

$X_{1} = 2(-1)^1 + 10 \cdot 3^0$ $8 = 8$

$X_2 = 2(-1)^2 + 10 \cdot 3^{1}$ $32 = 32$

Inductive Step: $i = k$

$X_k = 2(-1)^k + 10 \cdot 3^{k-1}$

Inductive Conclusion:

$X_{k+1} = X_k + X_{k-1}$

$X_{k+1} = 2(2(-1)^k + 10 \cdot 3^{k-1}) + 3(2(-1)^{k-1} + 10 \cdot 3^{k-2})$

$X_{k+1} = 4(-1)^k + 6(-1)^{k-1} + 20 \cdot 3^{k-1} + 10 \cdot 3^{k-1}$

At this point. I know I should factor, but the 2nd half of $3^{k-1}$ does not create $10\cdot3^{k+1}$ as needed.

Answer 1

You were close.

The base cases of $X_1 = 8$ and $X_2 = 32$ check out.

The formula to be verified is

$$X_k = [2 \times (-1)^{k}] + [10 \times 3^{(k-1)}].$$

The algorithm for expressing $X_{(k+1)}$ in terms of $X_k$ and $X_{(k-1)}$ is

$$X_{(k+1)} = [2 \times X_k] + [3 \times X_{(k-1)}].$$

Inductively assume that the formula holds for $X_k$ and $X_{(k-1)}.$

Then $$X_{(k+1)} = [2 \times X_k] + [3 \times X_{(k-1)}]$$

$$= 2 \times \{[2 \times (-1)^{k}] + [10 \times 3^{(k-1)}]\} + 3 \times \{[2 \times (-1)^{(k-1)}] + [10 \times 3^{(k-2)}]\}$$

$$= [2 \times (-1)^{(k-1)} \times (3-2)] + [10 \times 3^{(k-2)} \times (3 + <2\times 3>)]$$

$$= [2 \times (-1)^{(k+1)}] + [10 \times 3^{(k-2)} \times (9)]$$

$$= [2 \times (-1)^{k+1)}] + [10 \times 3^{(k)}].$$

This completes the inductive step.

Answer 2

Let $A_n = x_n-x_{n-2}$ and $B_n = x_n+x_{n-1}$

We're given that $$x_n=2x_{n-1}+3x_{n-2}$$ $$\implies x_n-x_{n-2}=2(x_{n-1}+x_{n-2})$$ $$\implies A_n=2B_{n-1}$$

Also, using the definitions of $A_n$ and $B_n$:

$$B_n - A_n = B_{n-1}$$

Thus, $$B_n = 3B_{n-1}$$

So, for general $B_n$: $$B_n = 3^{n-2}\cdot B_{2}$$ $$\implies B_n = 3^{n-2}\cdot 40$$

Now we can use $B_n$ to calculate $x_n$.

$$\implies x_n+x_{n-1} = 3^{n-2}\cdot 40$$

And, $$ x_{n+1}+x_{n} = 3^{n-1}\cdot 40$$

So, subtracting the above equations:

$$x_{n+1}-x_{n-1} = 80 \cdot 3^{n-2}$$

And so,

$$x_{n+1} = x_1 + 80 \cdot (1+3^2+3^4+...+3^{n-2})$$

This is true if $n$ is even.

If $n$ is odd,

$$x_{n+1} = x_2 + 240 \cdot (1+3^2+...+3^{n-3})$$

Thus, for odd n (summing up the geometric progression): $$x_{n+1}=10 \cdot 3^n +2$$

And for even n: $$x_{n+1}=10 \cdot 3^n-2$$

Which implies that $x_n=10 \cdot 3^{n-1} + 2 \cdot (-1)^n$.