1

I want to prove that $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$, where $F(0) = 0$, $F(1) = 1$ and for all $n \geq 2$, $F(n) = F(n-1) + F(n-2)$ without using induction. I want to prove it without induction because I want to implement the equation within another induction proof about Fibonacci numbers. Having 2 induction proofs together would be messy.

ThinkMan
  • 21
  • 2
    It depends what you mean by "messy". You could preface your proof by introducing a lemma (a helping theorem), and then proceed with the main proof; this is what authors of textbooks shoot for when writing their books. – Decaf-Math Oct 28 '18 at 01:05
  • I never prove this kind of statement without induction ¯\_(ツ)_/¯. – manooooh Oct 28 '18 at 01:07
  • 2
    Have you tried telescoping? By definition, $F_{j+2}-F_{j+1}=F_j$ for all $j=0,1,2,\ldots$, so $$\begin{align}F_{n+2}-F_1&=(F_{n+2}-F_{n+1})+(F_{n+1}-F_n)+\ldots+(F_2-F_1)\&=F_n+F_{n-1}+\ldots+F_0,.\end{align}$$ However, this is induction in disguise. – Batominovski Oct 28 '18 at 01:13
  • @Batominovski your proof is nice! And I think it does not use induction. Because $$\sum\limits_{i=0}^n F_i = \sum\limits_{i=0}^n (F_{i+2} - F_{i+1}) = \sum\limits_{i=0}^n F_{i+2} - \sum\limits_{i=0}^n F_{i+1} = \sum\limits_{j=2}^{n+2} F_j - \sum\limits_{j=1}^{n+1} F_j = F_{n+2} - F_1.$$ – with-forest Oct 28 '18 at 01:42
  • I don't think there's anything wrong with using induction here, as others have suggested - having this as a lemma is totally fine, because the inductions don't really 'nest' the way you're thinking about. That said, if you really want to prove it non-inductively you can always use the defintion of $F_n$ in terms of the golden ratio, $F_n=(1/\sqrt{5})(\phi^n-\phi^{-n})$, and then apply the formula for a finite geometric sum. – Steven Stadnicki Oct 28 '18 at 01:45
  • Depending on how you defined Fibonacci numbers... If you define $F(n)$ as the number of ways to climb $n$ stairs in steps and each step goes through 1 or 2 stairs, $F(k+2)$ is the way to climb $k+2$ stairs. On the other hand, there are $F(k)$ ways to climb $k+2$ stairs which the first step is 2 stairs, $F(k-1)$ ways the first step is 1 stair, and the second step is 2 stairs, $F(k-2)$ ways the first two steps are 1 stair and the third step is 2 stairs, and so on... Finally there is 1 way such that every step is 1 stair. – Hw Chu Oct 28 '18 at 02:14
  • 1
    @DoyunNam Writing a summation is inductive in nature, but this is more of a philosophical argument. – Batominovski Oct 28 '18 at 06:31

3 Answers3

0

Since you're trying to prove infinitely many statements, we either use induction or properties of the objects we're working with (in this case Fibonacci numbers). Hence, here is a proof using the latter. You may find it unsatisfying, but there aren't that many alternatives here.

We take as given the following two identities: $$\sum_{i=0}^{n-1} F_{2i+1}=F_{2n}$$ and $$\sum_{i=1}^n F_{2i}=F_{2n+1}-1$$

We add the two identities to get $$\sum_{i=1}^{2n}F_i=F_{2n}+F_{2n+1}-1=F_{2n+2}-1$$ Then we add $1$ to both sides, to get the desired identity for even $k$. To get it for odd $k$, we replace the second identity by $\sum_{i=1}^{n-1}F_{2i}=F_{2n-1}-1$, and proceed similarly.

vadim123
  • 82,796
0

Define the matrix

$$M=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$$

It's easy to see that the lower right hand entry of $M^n$ will have the same recurrence as the Fibonacci number. Checking the first few will show that $F(n) = M^{n+1}_{2,2}$. Similarly we can figure out for all the entries and see that

$$M^{n+1}=\begin{bmatrix}F(n+2) & F(n+1) \\ F(n+1) & F(n)\end{bmatrix}$$

We can write $F(n)=v^TM^{n+1}v$ for $v=[0\,\,1]^T$.

Now the sum can be writen as

$$S=\sum_{i=0}^kF(i)+1=\left(\sum_{i=0}^kv^TM^{i+1}v\right)+v^TIv=\sum_{i=0}^{k+1}v^TM^{i}v=v^T\left(\sum_{i=0}^{k+1}M^{i}\right)v$$

Now we simplify the polynomial in $M$ by noting that $M^{k+2}-I = (M-I)(\sum_{i=0}^{k+1}M^{i})$

$$S=v^T\left((M-I)^{-1}(M^{k+2}-I)\right)v$$

$$=v^T\left(\begin{bmatrix}0 & 1 \\1 & -1\end{bmatrix}^{-1}(M^{k+2}-I)\right)v$$

$$=v^T\left(M(M^{k+2}-I)\right)v$$

$$=v^T\left(M^{k+3}-M)\right)v$$

$$=v^TM^{k+3}v-v^TMv$$

$$=F(k+2)-F(0)$$

as desired.

rikhavshah
  • 1,355
0

Use the general term formula: $$F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}, \ \ \text{where} \ \ \phi=\frac{1+\sqrt{5}}{2}, \ \ \psi=\frac{1-\sqrt{5}}{2}.$$ Use the sum of geometric progression: $$\begin{align}\sum^{n}_{i=0}{F(i)} + 1 &= \frac{\phi^0-\psi^0}{\sqrt{5}}+\frac{\phi^1-\psi^1}{\sqrt{5}}+\cdots + \frac{\phi^n-\psi^n}{\sqrt{5}}+1=\\ &=\frac{1}{\sqrt{5}}([\phi^1+\phi^2+\cdots +\phi^n]-[\psi^1+\psi^2+\cdots +\psi^n])+1=\\ &=\frac{1}{\sqrt{5}}\cdot \left(\frac{\phi(\phi^n-1)}{\phi-1}-\frac{\psi(\psi^n-1)}{\psi-1}\right)+1=\\ &=\frac{1}{\sqrt{5}}\cdot \left(\frac{\phi(\phi^n-1)}{-\psi}-\frac{\psi(\psi^n-1)}{-\phi}\right)+1=\\ &=\frac{1}{\sqrt{5}}\cdot \frac{\phi^2(\phi^n-1)-\psi^2(\psi^n-1)}{-\psi\cdot \phi}+1=\\ &=\frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}+ \frac{-\phi^2+\psi^2}{\sqrt{5}}+1=\\ &=\frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}=\\ &=F(n+2).\end{align}$$

farruhota
  • 31,482