Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation.

I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints or suggestions?

share|improve this question
    
Write their formulas.... –  N. S. Nov 13 '11 at 22:40
    
@N.S. But it's messy for me... Are there any combinatorial proofs? –  Kou Nov 13 '11 at 22:43
4  
It is actually very easy, if you have the right formula, which is: $\binom{n-k+1}{k+1}=\binom{n-k}{k}+\binom{n-k}{k+1}$..The proof is two lines long.... The formula you posted is wrong, that's why you failed ... –  N. S. Nov 13 '11 at 22:48
    
For intuition, consider Pascal's triangle. Each binomial coefficient in the triangle is in exactly one of your $s_n$s, and every term that is in $s_n$ arises as the sum of a term from $s_{n-1}$ and a term from $s_{n-2}$, and this uses each term of $s_{n-1}$ and $s_{n-2}$ exactly once. –  Henning Makholm Nov 13 '11 at 23:08
    
@N.S. Well...$s_n=\sum_{k\geq 0}\binom{n-k+1}{k}$ Is it wrong? Why $\binom{n-k+1}{k+1}$? –  Kou Nov 14 '11 at 0:36

4 Answers 4

up vote 5 down vote accepted

Consider the words of length $n+1$ with letters 0,1 and no two consecutive 1s.

Proof that they are counted by the Fibonacci numbers.

Now count the same kind of words that contain exactly $k$ letters 1.

share|improve this answer

The problem with proving $\binom{n-k+1}k=\binom{n-k}k+\binom{n-k-1}k$ is that it is not true (try $k=0$ for starters). However for $n\geq1$ one has $$\begin{aligned} s_{n-1}&=\sum_{k=0}^{\lfloor\frac n2\rfloor}\binom{n-k}k\\ &= 1+\sum_{k=1}^{\lfloor\frac n2\rfloor}(\binom{n-1-k}k+\binom{n-1-k}{k-1})\\ &= 1+\sum_{k=1}^{\lfloor\frac {n-1}2\rfloor}\binom{n-1-k}k +\sum_{k=1}^{\lfloor\frac n2\rfloor}\binom{n-1-k}{k-1}\\ &= s_{n-2}+\sum_{k=0}^{\lfloor\frac n2\rfloor-1}\binom{n-2-k}k\\ &= s_{n-2}+s_{n-3},\\ \end{aligned} $$ so that the sequence $(s_n)_{n\geq-1}$ satisfies the Fibonacci recurrence (with $s_{-1}=\binom00=1$ by the same definition as $s_n$ for $n\in\mathbf N$). Since moreover $s_{-1}=s_0=1$ one has $s_n=F_{n+2}$ for all $n\geq-1$.

One wonders what is the point of starting the defining expression for $s_n$ with $\binom{n+1}0$, as the "$+1$" only increases the shift with respect to the Fibonacci sequence. To resume, one has $$ F_n=\sum_{k=0}^{\lfloor\frac{n-1}2\rfloor}\binom{n-1-k}k \qquad\text{for }n\geq1. $$

Added: although the summation runs into terms $0$ once $k>n/2$ (this is implicitly used in the argument above where we dropped the final term from the first summation in the third line), it should not be written as an unbounded (therefore infinite) summation: when one gets to terms for $k>n$, the terms are again nonzero, by the usual convention for binomial coefficients with negative upper index. This point should have been made clearer in the question.

share|improve this answer

This approach was explained in the above comments by N.S and and Henning


We can show $$\sum_{k\ge0} \binom{n-k}k=F_{n+1}$$ by induction.

Note that I did not specify the range for $k$. I am using the usual convention that $\binom pq$ is considered zero whenever $q<0$ or $q>p$. EDIT: After reading Marc van Leeuwen's answer I've realized, that this is true for non-negative $q$ only, so I've change range to $k\ge0$.

$1^\circ$ We can verify $n=-1,0,1,2$ by hand.

$2^\circ$ Inductive step: Suppose $n>1$. We want to show that this is true for $n+1$ and assume validity of the formula for $0,1,\dots,n$.

$$\sum_{k\ge0} \binom{n+1-k}k=\sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-k}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-1-(k-1)}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{j\ge0} \binom{n-1-j}{j}= F_{n+1}+F_n = F_{n+2}.$$


This proof can be visualized as follows: We are computing the sums of terms in Pascal triangle along diagonals.

It suffices to notice that each element on $k$-th diagonal is a sum of an element from $(k-1)$-th diagonal and $(k-2)$-th diagonal.

(I've taken the picture from thesis of my student I supervised some time ago. I am not sure whether she made the picture herself or found it somewhere on the Internet.)

PascalFib

share|improve this answer

We begin with the identity: $$ \binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}. $$ We apply the identity to $$ s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots $$ to get $$ s_n= \underbrace{\color{blue}{\binom{n}{0}} + \color{grey}{\binom{n}{-1}}}_{\text{first term}} + \underbrace{\color{blue}{\binom{n-1}{1}} + \color{brown}{\binom{n-1}{0}}}_{2\text{nd term}} + \underbrace{\color{blue}{\binom{n-2}{2}} + \color{brown}{\binom{n-2}{1}} }_{3\text{rd term}} + \cdots $$

Notice that the terms in are $\color{blue}{s_{n-1}}$ and those in brown/red $\color{brown}{s_{n-2}}$. (I had to work out what $s_{n-1}$ and $s_{n-2}$ was in order to catch the pattern, in case you're wondering how I knew). And so we have our fibonacci relation $$ s_n = \color{blue}{s_{n-1}} + \color{brown}{s_{n-2}} $$

As for the $\binom{n}{-1}$ term, just define it to be $0$...If that's not allowed, then wave your hands and mumble something.

share|improve this answer

Your Answer

 
discard

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.