For all we know

Here's an attempt to proof the following claim that I saw in @CompSciFact's Tweet earlier today.

(in case you don't know already, I am on twitter, find me @SubhayanRM :) )

Claim:

Let F[n] be the nth Fibonacci number. 

Then F[0] + F[1] + ... + F[n] = F[n+2] - 1.

Proof: (By induction)

We deine F[ i ] = F[ i - 1 ] + F[ i - 2 ]

and  F[-1] = 1

F[-2] = 0

i.e. We start from 1.  i.e F  = 1,2,3,5,8, ... 

however the proof is valid even if the you want to start from F=0,1,1,2 .. , just change the base case :), which is trivial and certainly holds true.

"I leave it up to the reader to verify" ;) 

The inductive hypothesis and the proof of it will be the same. 

Base Case:

  for n=1

  we have F[1] = 1 = 2-1 = F[2]-1

    so the base case holds true

Inductive Hypothesis: For purposes of induction we assume that proposition

  P(n) =  F[0] + F[1] + ... + F[n ] = F[n+2] - 1 

  is true

  so,

  P(n+1)

  = F[0] + F[1] + ... + F[k ] + F[k+1]

  = F[k+2] - 1 + F[k + 1]

  = F[k+1] + F[k+2] - 1

  = F[k+3] - 1

  = F[(k+1) + 2] - 1

So by laws of mathematical induction, P(n+1) is true whenever P(n) is true.  \qed