0
$\begingroup$

I'm working through the chapter 1 exercises of "Data Structures and Algorithm Analysis in Java" 3rd edition by Mark Allen Weiss. Exercise 11 a) in chapter 1 asks to prove the following:

$\sum_{i=1}^{n-2} F_i = F_n-2$

The wording of the question makes it sound like the above theorem is in fact true but I'm fairly certain it is false due to the following observations:

$\sum_{i=1}^{0-2} F_i = \sum_{i=1}^{-2} F_i = 0$ but $F_0 - 2 = 0 -2 = -2$

$\sum_{i=1}^{1-2} F_i = \sum_{i=1}^{-1} F_i = 0$ but $F_1 - 2 = 1 - 2 = -1$

$\sum_{i=1}^{2-2} F_i = \sum_{i=1}^{0} F_i = 0$ but $F_2 - 2 = 1- 2 = -1$

$\sum_{i=1}^{3-2} F_i = \sum_{i=1}^{1} F_i = F_1 = 1$ but $F_3 - 2 = 2 - 2 = 0$

$\sum_{i=1}^{4-2} F_i = \sum_{i=1}^{2} F_i = F_1 + F_2 = 1 + 1 = 2$ but $F_4 - 2 = 3 - 2 = 1$

$\sum_{i=1}^{5-2} F_i = \sum_{i=1}^{3} F_i = F_1 + F_2 + F_3 = 1 + 1 + 2 = 4$ but $F_5 - 2 = 5 - 2 = 3$

$\sum_{i=1}^{6-2} F_i = \sum_{i=1}^{4} F_i = F_1 + F_2 + F_3 + F_4 = 1 + 1 + 2 + 3 = 7$ but $F_6 - 2 = 8 - 2 = 6$

The question doesn't specify but I assume that its asking me to prove the theorem $\forall n \ge 0$ where the natural Fibonacci sequence starts. Am I missing something obvious here? or am I just overthinking it and have just proven the theorem false?

$\endgroup$

1 Answer 1

1
$\begingroup$

Take $F_0=1,\,F_1=1$, then assume $n\ge2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .