1
$\begingroup$

Given that $m_1= 2$ and $m_2 = 9$ and that $m_n = 2m_{n-1} + 3m_{n-2}$ for $n \geq 3$

This is what I've done so far.

$3^{n+1}$ = $3^n \cdot 3$

$3^{n+1} \geq 3 \cdot (2m_{n-1} + 3m_{n-2})$

$3^{n+1} \geq 6m_{n-1} + 9m_{n-2}$

$m_{n+1} = 7m_{n-1} + 6m_{n-2}$

Prove by induction.

2 Answers 2

3

By induction:

$m_{n+1}:=2m_n+3m_{n-1}\leq 2\cdot 3^n+3\cdot 3^{n-1}=3^n(2+1)=3^{n+1}$

  • 1
    @Eric: In practice you should make it automatic to think of strong induction and at the induction step simply assume that the proposition is true for **all** earlier values of $n$; if it turns out that you don’t actually need all of that assumption, no harm is done. (I think that the usual textbook approach of carefully distinguishing between strong and ordinary induction does the student no favor in the long run: they’re simply a special case and a **very** special case of the general notion of induction, and the sooner you can see them as at heart the same idea, the better off you’ll be.)2012-11-30
0

Hint $\ $ Both $\:3^n$ and $\rm\:m_n$ are solutions of $\rm\:f_{n+2} = 2\, f_{n+1} + 3\, f_n,\:$ therefore, by linearity, their difference $\rm\:f_n = 3^n\!-m_n\:$ is also a solution. But it is straightforward to prove by induction that $\rm\:f_1,f_2\ge 0\:$ $\Rightarrow$ $\rm\:f_n \ge 0,\:$ for all $\rm\:n\ge 1,\:$ because $\rm\:f_n,f_{n+1} \ge 0\:$ $\Rightarrow$ $\rm\:f_{n+2} = 2\,f_{n+1}+3\,f_n\ge 0.\:$ Therefore $\rm\: f_n = 3^n\! - m_n \ge 0,\:$ so $\rm\:3^n \ge m_n\:$

Remark $\ $ Note how reformulating it this way makes the essence of the matter obvious, viz. if the recurrence is an increasing function of the prior values, then if the sequence starts with initial values $\ge 0$ then it must remain $\ge 0$ for all greater values, since each successive step is increasing.

  • 0
    Aah ... got it. Thank you!2012-11-30