Homework Help

Prove that f(n+3) = 2f(n+1) + f(n) for all n is bigger than or equal to 1

user profile pic

alexward1352 | Student, Undergraduate | eNoter

Posted May 9, 2013 at 10:26 AM via web

dislike 2 like

Prove that f(n+3) = 2f(n+1) + f(n) for all n is bigger than or equal to 1

1 Answer | Add Yours

Top Answer

user profile pic

embizze | High School Teacher | (Level 1) Educator Emeritus

Posted May 11, 2013 at 6:17 PM (Answer #1)

dislike 2 like

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

f(k+4)=f(k+3)+f(k+2)

=2f(k+1)+f(k)+f(k+2) (But by definition f(k+2)=f(k+1)+f(k)) so

=f(k+1)+f(k+1)+f(k)+f(k+2)

=f(k+1)+f(k+2)+f(k+2)

=2f(k+2)+f(k+1) as required.

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes