2

So the question is:

$R_n=3(2^n)-4(5^n)$ for $n\ge 0$; prove that $R_n$ satisfies $R_n=7R_{n-1}-10R_{n-2}$.

I don't really know what to do from here. If I substitute

$$R_n = 3(2^n)-4(5^n)$$

into

$$Rn = 7R_{n-1}-10R_{n-2}$$

I end up getting

$$R_n = 7\Big(3(2^{n-1})-4(5^{n-1})\Big)-10\Big(3(2^{n-2})-4(5^{n-2})\Big)$$

Dont know what to do...

EDIT: Thanks to Zev, what I did was:

$$3(2^n)-4(5^n)=7\bigg[3(2^{n-1})-4(5^{n-1})\bigg]-10\bigg[3(2^{n-2})-4(5^{n-2})\bigg].$$ $$\begin{align*} 3(2^n)-4(5^n)&=21(2^{n-1})-28(5^{n-1})-30(2^{n-2})+40(5^{n-2})\\\\ 3(2^n)-4(5^n)&=21(2^{n})(2^{-1})-28(5^{n})(5^{-1})-30(2^{n})(2^{-2})+40(5^{n})(5^{-2})\\\\ 3(2^n)-4(5^n)&=21/2(2^{n})-28/5(5^{n})-30/2(2^{n})+40/5(5^{n})\\\\ 3(2^n)-4(5^n)&=(2^{n})[21/2-30/4]+(5^{n})[40/25-28/25]\\\\ 3(2^n)-4(5^n)&=(2^{n})[3]+(5^{n})[-4]\\\\ 3(2^n)-4(5^n)&=3(2^{n})-4(5^{n}) \end{align*}$$

MK3GTX
  • 25
  • You were missing some parentheses in that last expression; I added them. – Brian M. Scott May 29 '13 at 05:16
  • 1
    That's right so far; just go on. :-) If it helps you think more clearly, maybe you can let $2^{n-2} = x$ and $5^{n-2} = y$, so that $2^{n-1} = 2x$ and $5^{n-1} = 5y$, and finally $3(2^n) - 4(5^n) = 3(4x) - 4(25y)$. You're trying to show that that's the same as the RHS, which is $7(3(2x)-4(5y)) - 10(3x-4y)$. – ShreevatsaR May 29 '13 at 05:21

4 Answers4

1

You're on the right track so far; you've used the definition of $R_n$ to express the right side of the equation. Now just do this for the left side as well. You want to show that for any $n\geq 0$, $$3(2^n)-4(5^n)=7\bigg[3(2^{n-1})-4(5^{n-1})\bigg]-10\bigg[3(2^{n-2})-4(5^{n-2})\bigg].$$ This can be done directly: $$\begin{align*} 3(2^n)-4(5^n)&=21(2^{n-1})-28(5^{n-1})-30(2^{n-2})+40(5^{n-2})\\\\ 12(2^{n-2})-100(5^{n-2})&=42(2^{n-2})-140(5^{n-2})-30(2^{n-2})+40(5^{n-2}) \end{align*}$$

Zev Chonoles
  • 129,973
1

Having rewritten the recurrence, we get an equation:

$$10R_{n-2}-7R_{n-1}+R_n=0$$

that can easily be solved.

The roots of a characteristical polymomial $10-7k+k^2=0$ are $k_1=2,k_2=5$. So general solution is $R_n=c_12^{n}+c_25^{n}$, where $c_1$ and $c_2$ are arbitrary constants.

Тимофей Ломоносов
  • 768
0

We need to eliminate $2^n,3^n$

$$R_n=3\cdot 2^n-4\cdot 5^n \ \ \ \ (1)$$

$$(1)\implies 3\cdot2^n-5\cdot 5^n-R_n=0\ \ \ \ (2)$$

$$(1)\implies R_{n+1}=3\cdot 2^{n+1}-4\cdot 5^{n+1}=6\cdot2^n-20\cdot 5^n$$ $$\implies 6\cdot 2^n-20\cdot 5^n-R_{n+1}=0 \ \ \ \ (3)$$

Solving $(2),(3)$ for $2^n,3^n$ we get $$2^n=\frac{5R_n-R_{n+1}}9\text{ and } 3^n=\frac{2R_n-R_{n+1}}{12}$$

$$(1)\implies R_{n+2}=3\cdot 2^{n+2}-4\cdot 5^{n+2}=12\cdot2^n-100\cdot 5^n\ \ \ \ (4)$$

Put the values of $2^n,3^n$ in $(4)$

lab bhattacharjee
  • 274,582
0

Let $\,S\,$ be the shift operator: $\,S f_n = f_{n+1}.\,$ Note $\,(S\!-\!a)(ca^n)\! = ca^{n+1}\!-ca^{n+1} = 0.\,$ The recurrence is $\, 0 = (S^2\! - 7S + 10)f_n = (S\!-\!5)(S\!-\!2) f_n,\,$ which is easily verified as follows

$$\begin{eqnarray}(\color{#0a0}{S\!-\!2)2^n\! = 0}\\ \color{#c00}{(S\!-\!5)5^n\! = 0}\end{eqnarray}\!\Rightarrow (S\!-\!5)(\color{#0a0}{S\!-\!2})(\color{#0a0}{a2^n}\!+\!b5^n) = (S\!-\!5)(S\!-\!2)(b5^n) \stackrel{(\star)}= (S\!-\!2)(\color{#c00}{S\!-\!5})(\color{#c00}{b5^n}) = 0$$

$(\star)$ Key here is that that $\,S\!-\!5\,$ commutes with $\,S\!-\!2\,$ because they have constant coefficients, where $\,c\,$ constant means $\,Sc = cS,\,$ i.e. $\, S cf_n = cSf_n = cf_{n+1}$.

Key Ideas
  • 4,224