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
- A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
Combinatorial Proofs
- Combinatorial Proofs.
- Lucas' Theorem.
- Ways To Count.
- Geometric Proof of Wilson's Theorem.
- Partitioning a Circle
- A Minesweeper Theorem
- Another Binomial Identity with Proofs
- Counting Fat Sets
- Counting Permutations with Fixed Points
- Pythagorean Triples via Fibonacci Numbers
|Up| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1966-2016 Alexander Bogomolny
71493849