<s>[INST] I do not know how to solve for Induction Conclusion 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.
 [/INST] 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.
</s>