1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Sorry for the typos. $\endgroup$
    – jojanqo
    Oct 22 '20 at 4:42
  • $\begingroup$ @user2661923 there is the fix $\endgroup$
    – jojanqo
    Oct 22 '20 at 5:03
  • $\begingroup$ @user2661923 I am so sorry, I put the 2nd question after that as this statement, this should be right now. $\endgroup$
    – jojanqo
    Oct 22 '20 at 5:24
  • $\begingroup$ 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).$ $\endgroup$ Oct 22 '20 at 5:55
  • $\begingroup$ 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? $\endgroup$
    – jojanqo
    Oct 22 '20 at 6:05
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Oh, I just completely neglected the possibility of 9 ever occurring. Thank you very much.. $\endgroup$
    – jojanqo
    Oct 22 '20 at 6:58
  • $\begingroup$ Wait, could you explain the 3rd step of the last portion please? How did you get (3-2) and (3+ 2*3)? $\endgroup$
    – jojanqo
    Oct 22 '20 at 7:00
  • $\begingroup$ @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)}.$$ $\endgroup$ Oct 22 '20 at 7:08
  • $\begingroup$ Ah, I see, thank you. $\endgroup$
    – jojanqo
    Oct 22 '20 at 7:08
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Interesting take, I'll try it. $\endgroup$
    – jojanqo
    Oct 22 '20 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.