Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
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
1  
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
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.) –  Brian M. Scott Nov 30 '12 at 5:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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