Induction proof for Fibonacci sum different notation

306 Views Asked by At

This question was asked but using sum notation and I am trying to relate it to what I am doing.

I am trying to prove by induction that for the Fibonacci series, $a_1+a_2+...+a_n=a_{n+2}-1$ is true.

$1=a_1=a_{n+2}-1=2-1=1$ So it is true for the base case.

If $a_1+a_2+...+a_n=a_{k+2}-1$ is true for some k in the integers, then we want to show that

$a_1+a_2+...+a_k+a_{k+1}=a_{k+1+2}-1$

This is equal to:

$a_{k+2}-1+a_{k+1}=a_{k+1+2}-1$

$a_{k+2}+a_{k+1}=a_{k+1+2}$ Adding one to both sides.

I have checked this for various values of n and it holds, but I don't know how to show that these are equal. Is it just by definition of Fibonacci numbers?

1

There are 1 best solutions below

0
On

The inductive step consists in proving that $$ a_1+\dots+a_{k}+a_{k+1}=a_{(k+1)+2}-1 $$ once we assume that $a_1+\dots+a_{k}=a_{k+2}-1$. Now $$ a_1+\dots+a_{k}+a_{k+1}=(a_{k+2}-1)+a_{k+1} $$ and, by definition of the Fibonacci sequence, $$ a_{k+2}+a_{k+1}=a_{k+3} $$ so we have $$ a_1+\dots+a_{k}+a_{k+1}=a_{k+3}-1=a_{(k+1)+2}-1 $$

So, yes, your argument is good, although I'd prefer the formulation above.