750 Combinatorics and Probability
This formula follows inductively from the combinatorial identity
(
m
m
)
+
(
m+ 1
m)
+···+
(
m+p
m)
=
(
m+p+ 1
m+ 1)
,
which holds form, p≥0. This identity is quite straightforward and can be proved using
Pascal’s triangle as follows:
(
m
m
)
+
(
m+ 1
m)
+···+
(
m+p
m)
=
(
m+ 1
m+ 1)
+
(
m+ 1
m)
+···+
(
m+p
m)
=
(
m+ 2
m+ 1)
+
(
m+ 2
m)
+···+
(
m+p
m)
=
(
m+ 3
m+ 1)
+
(
m+ 3
m)
+···+
(
m+p
m)
= ··· =
(
m+p
m+ 1)
+
(
m+p
m)
=
(
m+p+ 1
m+ 1)
.
861.The general term of the Fibonacci sequence is given by the Binet formula
Fn=1
√
5
[(
1 +
√
5
2
)n
−(
1 −
√
5
2
)n]
,n≥ 0.Note that becauseF 0 =0, we can start the summation at the 0th term. We therefore have
∑ni= 0Fi(
n
i)
=
1
√
5
⎡
⎣
∑ni= 0(
n
i)(
1 +
√
5
2
)i
−∑ni= 0(
n
i)(
1 −
√
5
2
)i⎤
⎦=
1
√
5
[(
1 +
√
5
2
+ 1
)n
−(
1 −
√
5
2
+ 1
)n]=
1
√
5
[(
3 +
√
5
2
)n
−(
3 −
√
5
2
)n]
.But
3 ±√
5
2
=
(
1 ±
√
5
2
) 2
.
So the sum is equal to
1
√
5⎡
⎣
(
1 +
√
5
2
) 2 n
−(
1 −
√
5
2
) 2 n⎤
⎦,