The Fibonacci Numbers
We define the
n
-th fibonacci number as follows
F
0
=
0
and
F
1
=
1
F
n
=
F
n
−
1
+
F
n
−
2
for every
n
≥
2
Sum Equals Jump 2 minus One
For every
n
∈
N
0
we have
F
0
+
F
1
+
⋯
+
F
n
=
F
n
+
2
−
1
We prove it by induction, for the base case
F
(
0
+
2
)
−
1
=
(
F
1
+
F
0
)
−
1
=
1
+
0
−
1
=
0
=
F
0
as needed. Next assume it holds true for
k
∈
N
0
and then we want to prove that
F
k
+
3
−
1
=
F
0
+
…
+
F
k
+
1
, we can handle the sum with the inductive hypothesis, so that
F
0
+
…
+
F
k
+
F
k
+
1
=
(
F
k
+
2
−
1
)
+
F
k
+
1
=
F
k
+
3
−
1
as needed.