# Proof of the relationship between fibonacci numbers and pascal's triangle, without induction

I must prove, without induction, the relationship above is:

$$\sum _{ k=0 }^{ \lfloor n/2\rfloor}{ \binom{n-k}k } ={F}_{n+1}$$

I understand how the equation works but I have no idea how to prove it.

Thanks for any help!

-
Note, you can't even define this sort of question without induction. So you can't really prove it "without induction," you can just hide the induction in some supplemental theorem/lemma. – Thomas Andrews Aug 5 '13 at 23:18
Weird, my prof said to prove without induction. Perhaps he meant to just explain how we get to this equation? I'm not sure how the equation is derived... – Justin Aug 5 '13 at 23:20
It depends on what other theorems you are allowed to use - as I say, it is possible to "hide" induction by appealing to other theorems. – Thomas Andrews Aug 5 '13 at 23:21
Perhaps the exercise isn't to prove anything, but merely to convert the illustrated relation into a formal equation (as a prelude to later proof) ... but that's not much of an exercise. – Blue Aug 5 '13 at 23:22
For example, if you know a closed form for $\sum_{k=0}^\infty F_k z^k$, you can prove this theorem... – Thomas Andrews Aug 5 '13 at 23:23

$$\sum_{k=0}^\infty F_k z^k = \frac{z}{1-z-z^2}$$
Then you can prove this by using that $\frac{1}{1-w} = \sum_{k=0}^\infty w^k$ where $w=z+z^2$.
@Justin If you dislike the floor function, consider when $n$ is even and odd. – Pedro Tamaroff Aug 5 '13 at 23:29
The reason is just that if $k> n/2$, $n-k<k$, so $\binom{n-k}k = 0$. Therefore you could just write: $$\sum_{k=0}^n \binom{n-k}k$$ Obviously, if $k\leq n/2$ then $k\leq\lfloor n/2\rfloor$ - the end term of $\sum$ needs to be an integer. – Thomas Andrews Aug 5 '13 at 23:30
And to make the end an integer. If you just wrote $\sum_{k=0}^{n/2}$, that wouldn't make sense if $n$ was odd. – Thomas Andrews Aug 5 '13 at 23:37