# 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.

• Sorry for the typos. Oct 22 '20 at 4:42
• @user2661923 there is the fix Oct 22 '20 at 5:03
• @user2661923 I am so sorry, I put the 2nd question after that as this statement, this should be right now. Oct 22 '20 at 5:24
• I am not allowed to provide an answer until you show work. The assertion is now accurate. Re-express the assertion as $x_i = f(i)$, where you have been given the function $f(i)$. Then, prove the assertion via induction, by doing the math to prove that $\{[3 \times f(i-2)] + [2 \times f(i-1)]\} = f(i).$ Oct 22 '20 at 5:55
• Will do soon, I am outside rn. When I get inside, I'll showcase all that I have. When I get a supposed solution, or get stuck - may I ask for assistance? Oct 22 '20 at 6:05

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.

• Oh, I just completely neglected the possibility of 9 ever occurring. Thank you very much.. Oct 22 '20 at 6:58
• Wait, could you explain the 3rd step of the last portion please? How did you get (3-2) and (3+ 2*3)? Oct 22 '20 at 7:00
• @jojanqo $$2 \times 2 \times (-1)^k = (-4) \times (-1)^{(k-1)}.$$ $$(6 - 4) \times (-1)^{(k-1)} = 2 \times (-1)^{(k-1)}.$$ $$2 \times 10 \times 3^{(k-1)} = 6 \times 10 \times 3^{(k-2)}.$$ $$6 \times 10 \times 3^{(k-2)} + 3 \times 10 \times 3^{(k-2)} = 9 \times 10 \times 3^{(k-2)}.$$ Oct 22 '20 at 7:08
• Ah, I see, thank you. Oct 22 '20 at 7:08

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$$.

• Interesting take, I'll try it. Oct 22 '20 at 6:58