Better Students Ask More Questions.
Prove that f(n+3) = 2f(n+1) + f(n) for all n is bigger than or equal to 1
1 Answer | add yours
High School Teacher
Best answer as selected by question asker.
We proceed by induction:
(1) The base case n=1: f(4)=3=2+1=2f(2)+f(1) checks
(2) The inductive case:We assume there exists `k >= 1` such that f(k+3)=2f(k+1)+f(k)
(3) We need to show that for such a k, f(k+4)=2f(k+2)+f(k+1):
By definition f(k+4)=f(k+3)+f(k+2)
By the inductive step f(k+3)=2f(k+1)+f(k) so
=2f(k+1)+f(k)+f(k+2) (But by definition f(k+2)=f(k+1)+f(k)) so
=2f(k+2)+f(k+1) as required.
Posted by embizze on May 11, 2013 at 6:17 PM (Answer #1)
Join to answer this question
Join a community of thousands of dedicated teachers and students.