Question

Please solve this question by using Principle of Mathematical Inducation ​

Answer 1

you can do this problem using strong mathematical induction as you said.

First you have to examine the base case.

Base case n=1,2

Clearly F(1)=1<21=2 and F(2)=1<22=4

Now you assume that the claim works up to a positive integer k. i.e

F(k)<2k

Now you want to prove that F(k+1)<2k+1

We already know that F(k+1)=F(k)+F(k−1)

By our assumption we know that F(k)<2k and F(k−1)<2k−1

because we used strong mathematical induction and not just regular induction.

And so we have that F(k+1)<2k+2k−1<2k+2k=2(2k)=2k+1 and you are done □