4 a 8 points Use induction to prove that F3n is even for eve

4. (a) (8 points) Use induction to prove that F3n is even for every positive integer n, where Fn denotes the nth Fibonacci number. Assume F (b) (2 points Is the 100th Fibonacci number even or odd? You don\'t need a rigorous proof, but give a brief explanation of how you arrived at your answer.

Solution

4.Answer:

a)

Assumption: F₁=F₂=1

By using recursive formula,

F_n+1=F_n-1+F_n-2

When n=1,

F₃₍₁₎=F₂+F₁=1+1=2

Hence F_3n is even for n=1.

For all positive integers consider, n+1

F_3(n+1)=F_3n+3

  =F_3n+2+F_3n+1

=F_3n+1+F_3n+F_3n+1

=2F_3n+1+F_3n

Therefore, F_3n is even for every positive integer of n as n denotes nth number of fibonacci series.

b)

F₁=F₂=1

By using recursive formula,

F_n+1=F_n-1+F_n-2

F₃=F₂+F₁=1+1=2

F₄=F₃+F₂=2+1=3

F₅=F₄+F₃=3+2=5

F₆=F₅+F₄=5+3=8

The series 1,1,2,3,5,8

and the pattern is odd, odd, even,odd, odd, even.

Every 3rd number is even in the series. Hence the number divisible by 3 will be even else it will be odd.

100 is not divisible by 3 and therefore 100th fibonacci series is an odd number.