# Prove that $m_n \leq 3^n$ for all $n\in \Bbb{Z}_+$

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.

-

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.

-
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? –  Paresh Nov 30 '12 at 7:14
@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. –  Bill Dubuque Nov 30 '12 at 7:32
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. –  Paresh Nov 30 '12 at 7:49
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.\ \$ –  Bill Dubuque Nov 30 '12 at 8:22
Aah ... got it. Thank you! –  Paresh Nov 30 '12 at 9:31

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

-
I might add, since you (@Eric) seem to be learning to do proofs, that @DonAntonio used strong induction in his proof. –  anegligibleperson Nov 30 '12 at 4:18
Umm ok... i would have never thought of that –  Eric Nov 30 '12 at 4:23
Is it really strong induction? He didn't check for P(1) and P(2). –  Eric Nov 30 '12 at 4:24
Yes, it is @Eric, and I didn't check those two first because they're obvious from the given data. –  DonAntonio Nov 30 '12 at 4:35
@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.) –  Brian M. Scott Nov 30 '12 at 5:18