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

### 1 Answer | Add Yours

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.