Pythagorean Triples via Fibonacci Numbers

The purpose of this page is to establish an identity that involves the Fibonacci numbers $\{F_{n}\},$ $n\ge 0:$

(1)

$F_{n}^{2}+F_{n+1}^{2}=F_{2n+1},$ $n\ge 1.$

and derive from it another one that shows a construction of the Pythagorean triples:

(2)

$(F_{n-1}F_{n+2})^{2}+(2F_{n}F_{n+1})^{2}=(F_{2n+1})^{2}. $

where $n\ge 1.$ The Fibonacci numbers satisfy the recurrence relation

$F_{n+2} = F_{n+1} + F_{n},$

along with the initial conditions $F_{1} = 1$ and $F_{0} = 0.$

We offer a combinatorial proof of (1) based on counting the number $T_{n}$ of tilings of an $1\times n$ board with single and double square (dominoes) pieces. Elsewhere we found that $F_{n}=T_{n-1},$ $n\ge 0.$

Proof of (1)

In terms of the number of tilings $T_n,$ (1) appears as

(1')

$T_{n-1}^{2}+T_{n}^{2}=T_{2n},$ $n\ge 0.$

This is what we shall prove by counting the number of tilings of a $1\times 2n$ board which is T_{2n},$T_{2n-1}$,$T_{2n}$,$T_{2n+1}$,$T_{2n+2}$ differently. A $1\times 2n$ board may be looked at as a joint of two $1\times n$ boards. Each of this can be tiled in $T_n$ ways which accounts for the term T_{n}^{2},$T_{n}^{2}$,$T_{n-1}^{2}$. Where does the other term - $T_{n-1}^{2}$ - come from? If you look at the $1\times 2n$ again as a whole, the break line between the $n$th and $(n+1)$st squares may or may not be covered with a domino piece. If it's not, the tiling is counted in $T_{n}^{2}.$ But if it is, that domino piece splits the tiling into the tilings of two $1\times (n-1)$ boards, giving additional $T_{n-1}^{2}$ tilings.

Proof of (2)

All Pythagorean triples can be generated with two integers $a$ and $b$ as in $(a^{2}-b^{2})^{2}+(2ab)^{2}=$(a^{2}+b^{2})^{2},$a^{2}\times b^{2}$,$a^{2}\cdot b^{2}$,$(a^{2}+b^{2})^{2}$. From (1) it is obvious that for (2) to work, we need to take $a=F_{n+1}$ and $b=F_n.$ Thus, to demonstrate (2) we have to prove that

(3)

$F_{n-1}F_{n+2}=F_{n+1}^{2}-F_{n}^2,$ $n\ge 1.$

But, applying the recursive definition twice,

$\begin{align} F_{n+1}^{2}-F_{n}^2 &= (F_{n+1}-F_{n})(F_{n+1}+F_{n})\\ &=F_{n-1}\cdot F_{n+2}. \end{align}$

Exactly as required.

An extra identity

Replacing $n$ with $n-1$ in $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$ and subtracting the result, we obtain

$F_{n+1}^{2} - F_{n-1}^{2}=F_{2n+1}-F_{2n-1}=F_{2n}.$

Try to find a combinatorial argument to prove $F_{n+1}^{2} - F_{n-1}^{2}=F_{2n}$ independently.

Here is a hint: in terms of tilings, the identity appears as T_{n}^{2} - T_{n-2}^{2}=T_{2n-1},$T_{n}^{2} - T_{n-2}^{2}=T_{2(n-1)}$,$T_{n}^{2} - T_{n-2}^{2}=T_{2n-1}$. Consider the number of pairs of tilings of an $1\times n$ board of which at least,at least,at most,exactly one ends with a square.


References

  1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003

Combinatorial Proofs

  1. Combinatorial Proofs.
  2. Lucas' Theorem.
  3. Ways To Count.
  4. Geometric Proof of Wilson's Theorem.
  5. Partitioning a Circle
  6. A Minesweeper Theorem
  7. Another Binomial Identity with Proofs
  8. Counting Fat Sets
  9. Counting Permutations with Fixed Points
  10. Pythagorean Triples via Fibonacci Numbers

|Up| |Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1966-2016 Alexander Bogomolny

 61196840

Search by google: