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
    I might add, since you (@Eric) seem to be learning to do proofs, that @DonAntonio used strong induction in his proof.2012-11-30
  • 0
    Umm ok... i would have never thought of that2012-11-30
  • 0
    Is it really strong induction? He didn't check for P(1) and P(2).2012-11-30
  • 1
    Yes, it is @Eric, and I didn't check those two first because they're obvious from the given data.2012-11-30
  • 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
    When you say "by linearity, their difference is also a solution", can't you also say that $f_n = m_n - 3^n$ is also a solution by the same argument? In that case, won't the conclusion $m_n \ge 3^n$ also be correct? Am I missing something here?2012-11-30
  • 0
    @Paresh I don't know what the "same argument" refers to. If you mean that one could replace the appeal to linearity by brute force verification that $\rm\,3^n - m_n\,$ is a solution then, yes, one could do that, but it amounts to the same thing, with the higher-level (linear) conceptual structure stripped away.2012-11-30
  • 0
    Well, this is probably a stupid question. But I was thinking that by "linearity", you mean $f_n = \alpha 3^n + \beta m_n$ is also a solution. Which probably means $m_n - 3^n$ is also a solution. But, as you show, $f_n \ge 0$, but then that would mean $m_n \ge 3^n$. Why am I getting this contradiction? Sorry if I making some elementary mistake.2012-11-30
  • 0
    Yes, that's what linearity means. But the proof shows that *if* a solution $\rm\,f_n\,$ has initial conditions $\rm\:f_1,f_2 \ge 0\:$ then $\rm\,f_n$ remains $\ge 0$ for all $\rm\:n\ge 1.\:$ This is true for the solution $\rm\:f_n = 3^n - m_n\:$ since $\rm\:f_1 = 1,\, f_2 = 0,\:$ but it is false for $\rm\,\hat f_n = -f_n = m_n-3^n\:$ since $\rm\:\hat f_1 = -f_1 = -1\:$ is not $\ge 0.\ \ $2012-11-30
  • 0
    Aah ... got it. Thank you!2012-11-30