A couple weeks ago, while looking at word problems involving the Fibonacci sequence, we saw two answers to the same problem, one involving Fibonacci and the other using combinations that formed an interesting pattern in Pascal’s Triangle. I promised a proof of the relationship, and it’s time to do that. And while we’re there, since we’ve been exploring inductive proofs, let’s take a look at Pascal’s Triangle itself.
Fibonacci and Pascal’s Triangle
Let’s start with this 2003 question, as a teaser for our goal:
Fibonacci Numbers in Pascal's Triangle How do you find the Fibonacci numbers in Pascal's Triangle?
Doctor Rob answered by showing the interesting pattern I mentioned before:
Add numbers along the diagonals of the triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
21 35 35 21 7 1
70 56 28 8 1
84 36 9 1
45 10 1
11 1
1
1 + 21 + 70 + 84 + 45 + 11 + 1 = 233 = F(13)
6 + 35 + 56 + 36 + 10 + 1 = 144 = F(12)
1 + 15 + 35 + 28 + 9 + 1 = 89 = F(11)
5 + 20 + 21 + 8 + 1 = 55 = F(10)
and so on.
We’ll be seeing a proof; but first, I want to explore Pascal’s Triangle:
Pascal’s Triangle and binomial coefficients
In case you are not familiar with Pascal’s Triangle, here is an introductory question from 1996.
Binomial Expansions and Pascal's Triangle Can you supply the definition of what a binomial expansion is, where it would be used, why, and how to do one?
Doctor Pete gave a thorough introduction to binomial coefficients, which are the components of Pascal’s Triangle:
A *binomial* is a polynomial expression with two terms, like x+y, x^2+1 (x squared plus 1), or x^4-3*x. *Binomial expansion* refers to a formula by which one can "expand out" expressions like (x+y)^5 and (3*x+2)^n, where the entire binomial is raised to some power. Usually, binomial expansion is introduced using a construction called Pascal's Triangle, but I prefer to think of it in terms of something called the *binomial coefficient*, which I'll explain later. First, we'll look at the "generic" binomial x+y, and its powers (x+y)^2, (x+y)^3, ... (x+y)^n. Notice the following: (x+y)^1 = x+y (x+y)^2 = (x+y)(x+y) = x^2+2*x*y+y^2 (x+y)^3 = (x+y)(x+y)^2 = x^3+3*x^2*y+3*x*y^2+y^3 (x+y)^4 = (x+y)(x+y)^3 = x^4+4*x^3*y+6*x^2*y^2+4*x*y^3+y^4 ...
At each step, we are multiplying what we already have in the previous step, by the same binomial yet again, distributing. For example, at the last step, we have $$(x+y)^4 = (x+y)(x+y)^3 = (x+y)(x^3+3x^2y+3xy^2+y^3)\\ = x(x^3+3x^2y+3xy^2+y^3)+y(x^3+3x^2y+3xy^2+y^3)\\ = (x^4+3x^3y+3x^2y^2+xy^3)\\+(x^3y+3x^2y^2+3xy^3+y^4)\\ = x^4+(3+1)x^3y+(3+3)x^2y^2+(1+3)xy^3+y^4\\ = x^4+4x^3y+6x^2y^2+4xy^3+y^4.$$ The way I wrote the next-to-last line gives a hint to the pattern we will be working with, and to its proof.
What kind of patterns can we see from this? Well, there are two things going on here, namely the powers of x and y, and the coefficients. Let's look at the powers:
Power of (x,y) in the (k)th term:
k=1 k=2 k=3 k=4 k=5
(x+y)^1: (1,0) (0,1)
(x+y)^2: (2,0) (1,1) (0,2)
(x+y)^3: (3,0) (2,1) (1,2) (0,3)
(x+y)^4: (4,0) (3,1) (2,2) (1,3) (0,4)
Clearly, (x+y)^n will have n+1 terms, and we can infer from the above that the (k)th term will have a (n-k+1)th power of x, and a (k-1)th power of y.
As you work through the terms, the powers of x go from n down to 0 (for \(n+1\) terms), while the powers of y go from 0 up to n.
Now, let's look at the coefficients:
Coefficient in the (k)th term:
k=1 k=2 k=3 k=4 k=5
(x+y)^1: 1 1
(x+y)^2: 1 2 1
(x+y)^3: 1 3 3 1
(x+y)^4: 1 4 6 4 1
Now, this pattern isn't so clear.... Let's write it like this:
Row 0: (1) < I added this just for fun, it'll
1: 1 1 become clear why I did later
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
This arrangement of numbers is Pascal’s Triangle; and the numbers in it are called binomial coefficients.
Notice that any entry above which isn't 1 is the sum of the two entries diagonally above it: For example, the 6 is 3+3. This is Pascal's Triangle, and it is easy to see how to generate any row: just put 1's along the sides, and add pairs of values from the previous row to get the next. For example, the next row will be 1 5 10 10 5 1, the next after that will be 1 6 15 20 15 6 1, and so on. Is it a coincidence that the (n)th row corresponds to the coefficients of the expansion (x+y)^n? Not at all. Sidenote: Note I added a (0)th row to the triangle; it's not just there to make the figure a pretty triangle, but it actually corresponds to (x+y)^0 = 1, so it has a valid mathematical interpretation.
You can see the same additions, (3+1, 3+3, 1+3) in my expansion above.
Finally, we have a systematic approach to finding the expansion of (x+y)^n. Let B(n,k) be the (k)th entry in the (n)th row of Pascal's Triangle. Then
(x+y)^n = B(n,1)*x^n + B(n,2)*x^(n-1)*y + ... + B(n,n+1)*y^n,
or in summation notation,
n+1
\---\
(x+y)^n = > B(n,k)*x^(n-k+1)*y^(k-1) .
/---/
k=1
The notation B(n, k) is not standard, but temporary.
Now, is there an easy way to compute B(n,k)? That is, how can you find B(n,k) without having to write all these rows of Pascal's Triangle? Well, yes, there is, which is precisely why there exists a connection between Pascal's Triangle and the binomial expansion formula. But first, notice that it's easier to start with k = 0 rather than k = 1 in the above formula; so we'll count starting from the (0)th term, rather than the first. Our formula becomes
n
\---\
(x+y)^n = > C(n,k)*x^(n-k)*y^k ,
/---/
k=0
where C(n,k) = B(n,k+1). We call C(n,k) a *binomial coefficient*. It has the value
n!
C(n,k) = -------- ,
k!(n-k)!
where n! (read "n factorial"), is 1*2*3*...*n (so 3! = 1*2*3 = 6, for example, and 0! = 1). In combinatorics, it is also called "the number of combinations of n objects taken k at a time."
The binomial coefficient is also written as \({n\choose k}\) or \(_n C_k\), and often read “n choose k“.
You can see why I like to think of binomial expansions in terms of binomial coefficients: it's direct and simple. Pascal's Triangle is a useful way to learn about binomial expansion, but is very inconvenient to use. Now, I'll leave you with two exercises, the first easy, the second a bit more difficult: 1) Show that C(n,k) = C(n,n-k). 2) Show that C(n,k) indeed corresponds to the (k)th entry in the (n)th row of Pascal's Triangle. (Remember to count from k=0 and n=0.)
The first fact expresses the symmetry of the triangle; each row reads the same from both ends. You can explain it in many ways, from the way the triangle is built (by adding in the same way from either end), or from the binomial expansion (in which swapping x and y to make \((y+x)^n\) would reverse a row), or from the concept of combinations (since there are just as many ways to choose k of n items to include as to choose \(n-k\) items to exclude).
Here's a hint: Show that C(n,0) = C(n,n) = 1, since 0!=1; this establishes the "sides" of the triangle. Then show that C(n,k) = C(n-1,k-1) + C(n-1,k) for 1 <= k <= n-1; this establishes the "add the diagonals" property in Pascal's Triangle.
One way to do this is with induction, which we’ll explore next, on the way to our goal.
The Binomial Theorem
We got this question from Scott in 1996:
Binomial Theorem by Induction I'm trying to prove the Binomial Theorem by Induction. So (x+y)^n = the sum of as the series goes from j=0 to n, (n choose j)x^(n-j)y^j. Okay the base case is simple. We assume if it's true for n, to derive it's true for n+1. I've written out what the series looks like for n. Then I write out what it looks like for n+1, hoping I can apply the Pascal Identity to end up with (x+y)^n (x+y) which equals (x+y)^(n+1). But I can't. I'm thinking there must be some "trick" that I'm not seeing.
The Binomial Theorem, as stated here and above, is $$(x+y)^n = \sum_{j=0}^n{n\choose j}x^{n-j}y^j.$$ What Scott is calling the Pascal Identity is the addition rule discussed above, which we can write as $${n\choose r}+{n\choose {r+1}}={{n+1}\choose{r+1}}.$$ (We’ll be formally proving that soon.)
Doctor Anthony answered, using an alternate formulation with \((1+x)^n\):
To prove the binomial theorem by induction we use the fact that nCr + nC(r+1) = (n+1)C(r+1) We can see the binomial expansion of (1+x)^n is true for n = 1. Assume it is true for (1+x)^n = 1 + nC1*x + nC2*x^2 + ....+ nCr*x^r + nC(r+1)*x^(r+1) + ... Now multiply by (1+x) and find the new coefficient of x^(r+1). We get it by multiplying x by nCr*x^r and also by multiplying 1 by nC(r+1)*x^(r+1). So coefficient of x^(r+1) will be nCr + nC(r+1) = (n+1)C(r+1) Thus (1+x)^(n+1) = 1 + (n+1)C1*x + .... +(n+1)C(r+1)x^(r+1) + ... and this is the same series as before with n replaced by n+1 (and an extra term x^(n+1)) So if the series was correct for n, then it is also true for n+1. But it is true for n = 1, therefore for n = 2, therefore for n = 3, and so on to all positive, integral values of n.
This is the standard form for an inductive proof; it is the algebra that is troubling Scott.
Scott replied,
Doctor Anthony tried to help me with this problem but I'm afraid I don't understand. He says that "n choose r" + "n choose r+1" is equal to "n+1 choose r+1". How is that so? Pascal's Theorem? Also, the binomial theorem results in (x+y)^n, which I try to prove for (x+y)^(n+1). The Doctor's hints are all about (x+1). Where is y? I really do appreciate your further help.
A couple little things are blocking his view of the solution. One appears to be that the form of Pascal’s Identity (or Theorem) that Doctor Anthony stated is somehow different from what Scott has seen; another is that he changed the theorem from \((x+y)^n\) to \((1+x)^n\). These theorems are equivalent, but Scott needs help to see it. For the record, if we prove the theorem about \((1+x)^n\), then we can replace x with \(y/x\) and multiply the result by \(x^n\) to get \(x^n(1+\frac{y}{x})^n = (x+y)^n\), and the theorem in the general case will appear.
Proving Pascal’s Identity
Doctor Pete stepped in to attempt an explanation closer to Scott’s needs:
I've looked over the information so far. I will introduce a slightly different notation for the binomial coefficient: Let "n choose r," or nCr, be written as C(n,r). Now, let's address your first question, which is to show that
C(n,r) + C(n,r+1) = C(n+1,r+1) .
To do this, we must appeal to the definition of C(n,r), which is the number of combinations of n objects taken r at a time.
n!
C(n,r) = --------- .
(n-r)! r!
So we’re going to prove Pascal’s Identity, which Scott had mentioned without stating whether he needed a proof, but then seemed unsure of; this will be the main piece we will use below for Fibonacci. This could be proved in several ways, as I mentioned earlier; he chooses a purely algebraic approach, adding fractions using a common denominator and using properties of factorials:
Therefore,
n! n!
C(n,r) + C(n,r+1) = --------- + ---------------
(n-r)! r! (n-r-1)! (r+1)!
n! (r+1) n! (n-r)
= ------------- + -------------
(n-r)! (r+1)! (n-r)! (r+1)!
n! (n-r+r+1)
= -------------
(n-r)! (r+1)!
(n+1)!
= -------------------
(n+1-(r+1))! (r+1)!
= C(n+1,r+1) .
Proving the Binomial Theorem by induction
Thus each binomial coefficient in the triangle is the sum of the two numbers above it.
As for your second question, notice that the central part of Dr. Anthony's proof is showing that the coefficients "transfer over" into the next case, using the fact we just proved above in response to your first question. The use of (x+1)^n as opposed to (x+y)^n doesn't make too much of a difference, as it is easy to generalize and replace the "1" with "y."
For concreteness, however, we'll do this:
(x+y)^n = Sum[C(n,k) x^k y^(n-k), {k,0,n}]
=> (x+y)^(n+1) = (x+y)Sum[C(n,k) x^k y^(n-k), {k,0,n}]
= Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n}]
+ Sum[C(n,k) x^k y^(n-k+1), {k,0,n}]
= Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n}]
+ Sum[C(n,k+1) x^(k+1) y^(n-k), {k,-1,n-1}]
= Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n-1}]
+ C(n,n) x^(n+1) y^0 + C(n,0) x^0 y^(n+1)
+ Sum[C(n,k+1) x^(k+1) y^(n-k), {k,0,n-1}]
= Sum[(C(n,k)+C(n,k+1)) x^(k+1) y^(n-k), {k,0,n-1}]
+ x^(n+1) + y^(n+1)
= Sum[C(n+1,k+1) x^(k+1) y^(n-k), {k,0,n-1}]
+ x^(n+1) + y^(n+1)
= Sum[C(n+1,k) x^k y^(n+1-k), {k,1,n}] + x^(n+1)
+ y^(n+1)
= Sum[C(n+1,k) x^k y^(n+1-k), {k,0,n+1}] .
The notation here is a little hard to follow; let’s examine it.
The induction hypothesis is $$(x+y)^n = \sum_{k=0}^n{n\choose k}x^ky^{n-k}.$$ (You may notice that this is reversed from Scott’s form, which had decreasing powers of x; this has increasing powers of x, but is otherwise identical.) We assume this is true for some particular \(n\); we want to show that it is also true for \(n+1\): $$(x+y)^{n+1} = \sum_{k=0}^{n+1}{{n+1}\choose k}x^ky^{n+1-k}.$$ And in fact,
$$(x+y)^{n+1} = (x+y)(x+y)^n\\ = (x+y)\sum_{k=0}^n{n\choose k}x^ky^{n-k}\\ = x\sum_{k=0}^n{n\choose k}x^ky^{n-k}+y\sum_{k=0}^n{n\choose k}x^ky^{n-k}\\ = \sum_{k=0}^n{n\choose k}x^{k+1}y^{n-k}+\sum_{k=0}^n{n\choose k}x^ky^{n-k+1}\\ = \sum_{k=0}^n{n\choose k}x^{k+1}y^{n-k}+\sum_{k=-1}^{n-1}{n\choose {k+1}}x^{k+1}y^{n-k}.$$
Here we replaced k with k + 1 in the second sum; next, we split off the last term in the first sum and the first term in the second sum:
$$ = \sum_{k=0}^{n-1}{n\choose k}x^{k+1}y^{n-k}+{n\choose n}x^{n+1}y^{n-n}\\+{n\choose {-1+1}}x^{-1+1}y^{n-(-1)}+\sum_{k=0}^{n-1}{n\choose {k+1}}x^{k+1}y^{n-k}\\ = \sum_{k=0}^{n-1}\left({n\choose k}+{n\choose {k+1}}\right)x^{k+1}y^{n-k}+x^{n+1}+y^{n+1}\\ = \sum_{k=0}^{n-1}{{n+1}\choose {k+1}}x^{k+1}y^{n-k}+x^{n+1}+y^{n+1}\\ = y^{n+1}+\sum_{k=1}^{n}{{n+1}\choose {k}}x^{k}y^{n-k+1}+x^{n+1}\\ = \sum_{k=0}^{n+1}{{n+1}\choose {k}}x^{k}y^{n+1-k},$$
which was our goal. (In the next to last line, we replaced \(k\) with \(k-1\).)
Thus, our statement is true from the induction hypothesis (i.e., the assumption that (x+y)^n = Sum[C(n,k) x^k y^(n-k), {k,0,n}]. (I hope this wasn't too difficult to follow.... For example, Sum[k, {k,0,n}] means "the sum of k from k=0 to k=n." There's a lot of subtle sum manipulation, but I prefer to do it this way rather than writing out things like "C(n,0) x^0 y^n + C(n,1) x^1 y^(n-1) + ...", because it's more rigorous.)
I hope this clears things up.
So we’ve proved Pascal’s Identity (sum formula) and the Binomial Theorem, and we’re ready for our ultimate goal:
Proving Fibonacci is in the triangle
I found that last page because it is referred to in the answer to this 2002 question:
Pascal's Triangle and Fibonacci Formula The diagonals of Pascal's triangle give the Fibonacci numbers. As the numbers are also binomial coefficients, I wrote down some equations of the diagonals: (0,0) = 1 (1,0) = 1 (2,0)+(1,1) = 2 (3,0)+(2,1) = 3 (4,0)+(3,1)+(2,2) = 5 (5,0)+(4,1)+(3,2)=1+4+3 = 8 (6,0)+(5,1)+(4,2)+(3,3) = 1+5+6+1 = 13 (7,0)+(6,1)+(5,2)+(4,3) = 1+6+10+4 = 21 (8,0)+(7,1)+(6,2)+(5,3)+(4,4) = 1+7+15+10+1 = 54 so I tried to create a formula fib(n) = sum_{k=0}^{n/2} {n-1-k,k} I would like to know if this formula is correct. I looked this problem up on the Web and on R. Knott's site and found two unrelated formulas: fib(n) = sum_{k=0}^{n-1} {n-k-1,k} fib(n) = sum_{k=1}^{n} {n-k,k-1} I plugged in numbers and it didn't work. Maybe I'm wrong. I don't know. I then found a formula of Lucas, 1876 F(n+1) = sum_{i=0}^{n/2} {n-i,i} n>=0 I think this is the same as mine, no? My thing to do was to prove why the diagonals of Pascal's triangle are the Fibonacci numbers by myself. Is what I did enough for 'my proof'?
Yael is using a non-standard notation for the binomial coefficient, (n, k) or {n, k}.
We’ve mentioned Ron Knott’s site before; the two quoted formulas are from
The Fibonacci Numbers in Pascal’s Triangle
$$F_n = \sum_{k=0}^{n-1} {{n-k-1}\choose{k}}$$
$$F_n = \sum_{k=1}^{n} {{n-k}\choose{k-1}}$$
The second comes from the first by replacing \(k\) with \(k – 1\). Both produce the same sums:
$$F_1=\sum_{k=0}^{0} {{-k}\choose{k}} = {{0}\choose{0}} = 1\\ F_2=\sum_{k=0}^{1} {{1-k}\choose{k}} = {{1}\choose{0}}+{{0}\choose{1}} = 1+0=1\\ F_3=\sum_{k=0}^{2} {{2-k}\choose{k}} = {{2}\choose{0}}+{{1}\choose{1}}+{{0}\choose{2}} = 1+1+0=2\\ F_4=\sum_{k=0}^{3} {{3-k}\choose{k}} = {{3}\choose{0}}+{{2}\choose{1}}+{{1}\choose{2}}+{{0}\choose{3}} = 1+2+0+0=3,$$
if we define \({n\choose r}=0\) when \(n<r\).
The site has a nice representation of these diagonals:
Yael’s summation,
$$F_n = \sum_{k=0}^{n/2} {{n-1-k}\choose{k}},$$
is identical except for a different upper limit, and produces the same summation with fewer extra zero terms, as long as you interpret a non-integer upper limit correctly:
$$F_1 = \sum_{k=0}^{1/2} {{-k}\choose{k}} = {{0}\choose{0}} = 1\\ F_2 = \sum_{k=0}^{1} {{1-k}\choose{k}} = {{0}\choose{0}}+{{0}\choose{1}} = 1+0 = 1\\ F_3 = \sum_{k=0}^{3/2} {{2-k}\choose{k}} = {{2}\choose{0}}+{{1}\choose{1}} = 1+1 = 2\\ F_4 = \sum_{k=0}^{2} {{3-k}\choose{k}} = {{3}\choose{0}}+{{2}\choose{1}}+{{1}\choose{2}} = 1+2+0 = 3.$$
So his just does a somewhat better job of counting terms, though not perfect. (We’ll improve it.)
Doctor Floor answered:
Hi, Yael, The way to formulate the theorem of connecting the Fibonacci numbers and Pascal's theorem you attribute to Lucas is correct, and I think useful as well. The only thing is that the n/2 would better be floor(n/2), where floor(p) is the largest integer smaller than p. The formula on Ron Knott's pages uses the extra assumption that if n<k then (n,k)=0; with that assumption his formulae are correct as well.
I find a slightly better form in Wikipedia:
$$F_n = \sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor} {{n-k-1}\choose{k}}.$$
This eliminates all 0 terms in my examples above.
But we still haven’t see a proof, so let’s go:
For the proof I think it would be good to use mathematical induction. You show that f(1) = f(2) = 1 with your formula, and that f(n+2) = f(n+1) + f(n). Perhaps the easiest way to prove this last step is to distinguish even and odd n. It think it is a good idea to use the formula: (n,r) + (n,r+1) = (n+1,r+1) I hope this puts you on track.
He has done the first steps of the induction, and suggested the Pascal Identity we saw above as a hint.
Yael responded:
As you say: f(n+2) = f(n+1) + f(n)
So, sum_{k=0}^{floor((n+2)/2)} {n+1-k,k} =
sum_{k=0}^{floor((n+1)/2)} {n-k,k} + sum_{k=0}^{floor(n/2)}
{n-1-k,k} (*)
[with floor meaning in your sense largest integer smaller than p]
I have tried to work on this for an hour, but can't seem to get to something useful.
I know you said it is a good idea to use the formula
(n,r) + (n,r+1) = (n+1,r+1)
but I didn't get that at all...sorry... I mean if you plug in numbers, I saw all right that this formula is true, but I didn't get the connection to the other formula we had (the sum one)...
Please could you help me with solving this -->(*). You said one should separate it into even and odd, so could you at least do it for even n's, please?
Thank you so much for taking time to help me out.
He has started the inductive step, using n + 1, but got stuck; and seems unfamiliar with our Pascal Identity (or at least doesn’t yet see where to use it).
Doctor Floor answered, referring to our proof of the identity above:
First, for the formula (n,r) + (n,r+1) = (n+1,r+1) [**], where we still assume that (n,r) = n C r, see the Dr. Math archives at Binomial Theorem by Induction http://mathforum.org/dr.math/problems/turner.7.14.96.html This is also just the addition rule for Pascal's triangle (each entry is the sum of the two entries above it).
Then he corrects the upper limit to agree with the formula I found in Wikipedia above:
Then, you gave the formula to prove
sum_{k=0}^{floor((n+2)/2)} (n+1-k,k) =
sum_{k=0}^{floor((n+1)/2)} (n-k,k) + sum_{k=0}^{floor(n/2)} (n-1-k,k).
This needs a little adjustment according to the formula you gave, and it seems correct,
fib(n) = sum_{k=0}^{floor((n-1)/2)} {n-1-k,k}.
Your formula (*) should thus be
sum_{k=0}^{floor((n+1)/2)} (n+1-k,k) =
sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2)} (n-1-k,k).
This is the corrected goal for the inductive step.
Now, as he said previously, it will be easiest to prove using separate cases for even and odd n, because of the floor function:
Using formula [**] we will prove this identity.
Case 1, n = even:
When n is even, then floor((n+1)/2) = floor(n/2) = n/2 and floor((n-1)/2) = n/2-1. Hence we have
sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) =
sum_{k=0}^{n/2} (n-k,k) + sum_{k=0}^{n/2-1} (n-1-k,k) =
<substitute k' = k+1 in the second sum>
sum_{k=0}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) =
(n,0) + sum_{k=1}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) =
1 + sum_{k=1}^{n/2} [(n-k,k) + (n-k,k-1)] =
<use formula [**]>
(n+1,0) + sum_{k=1}^{n/2} (n-k+1,k) = sum_{k=0}^{n/2} (n-k+1,k)
as desired.
The odd case is similar:
Case 2, n = odd:
When n is odd, then floor((n-1)/2) = floor(n/2) = (n-1)/2 and floor((n+1)/2) = (n+1)/2. Hence we have
sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) =
sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k=0}^{(n-1)/2-1} (n-1-k,k) =
<substitute k' = k+1 in the second sum>
sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k'=1}^{(n+1)/2} (n-k',k'-1) =
(n,0) + sum_{k=1}^{(n-1)/2} (n-k,k) + ((n-1)/2,(n-1)/2)
+ sum_{k'=1}^{(n-1)/2} (n-k',k'-1) =
2 + sum_{k=1}^{(n-1)/2} [(n-k,k) + (n-k,k-1)] =
<use formula [**]>
(n+1,0) +((n+1)/2,(n+1)/2) + sum_{k=1}^{(n-1)/2} (n-k+1,k) =
sum_{k=0}^{(n+1)/2} (n-k+1,k)
as desired.
And there we have it.
Now go back to Ron Knott’s site, where you’ll find a quick version of the same proof, just looking at the triangle!
I have not read a book on easy Fibonacci problems/proofs for decades. Do these books mention that the sum of the squares of the first n F numbers equals the product of the nth and n+1st? Leads to an induction proof that is even easier for beginning students to understand than 1+2+…+n=n(n+1)/2.
Yes, this fact is fairly well-known. I find it here as equation (25), \(\sum_{k=1}^{n}F_k^2 = F_nF_{n+1}\). The quick inductive proof you probably have in mind is presented in Wikipedia here.
If you’re interested in reading more on the subject, in addition to those two sites, you should definitely consider the source I’ve referred to several times, by Ron Knott, and a big list of proofs (including yours) at ProofWiki.