Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 1 down vote accepted

If you know that:

$$\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$.

share|cite|improve this answer
We haven't discussed this in class so I'm assuming we just have to explain the equation. For example, why do we use the floor function? – Justin Aug 5 '13 at 23:28
@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
So the floor function is only used to avoid making unnecessary calculations (i.e. adding zero to the sum)? – Justin Aug 5 '13 at 23:34
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.