A long time ago, I came across this problem:
Prove that
\[\frac{\pi}{4}=\tan^{-1}\frac{1}{2}+\tan^{-1}\frac{1}{5}+\tan^{-1}\frac{1}{13}+\tan^{-1}\frac{1}{34}+\dots \]where the denominators on the right are alternate numbers in the Fibonacci sequence. To put it more succinctly (but in a form that is less friendly)
\[\begin{aligned} \frac{\pi}{4}= \sum_{r=1}^\infty \tan^{-1}\frac{1}{\text{Fib}_{2r+1}} \end{aligned}\]This result is truly surprising and it's the subject of another article
We can test it out. Here is the Fibonacci sequence: \[0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;\dots\]
where \(F_0=0,\; F_1=1,\;F_2=1,\;\dots\)
Try \(F_{4}^{\;2}-F_3 F_{5}\), for example. Try \(F_{5}^{\;2}-F_4 F_{6}\), and so on. You'll soon see that it appears to be true. Proving that it is always true is a bit harder.
We can prove it by induction (not so easily; again, see
If \(A=\begin{pmatrix}1&1\\1&0\end{pmatrix}\), what is \(A^n\)?
\[\begin{aligned} A^2&=\begin{pmatrix}1& 1\\1&0\end{pmatrix}=\begin{pmatrix}2& 1\\1&1\end{pmatrix}\\ A^3&=\begin{pmatrix}2&\ 1\\1&1\end{pmatrix}\begin{pmatrix}1& 1\\1&0\end{pmatrix}\begin{pmatrix}1& 1\\1&0\end{pmatrix}=\begin{pmatrix}3& 2\\2&1\end{pmatrix}\\ A^4&=\begin{pmatrix}3& 2\\2&1\end{pmatrix}\begin{pmatrix}1& 1\\1&0\end{pmatrix}=\begin{pmatrix}5& 3\\3&2\end{pmatrix}\\ A^5&=\begin{pmatrix}5& 3\\3&2\end{pmatrix}\begin{pmatrix}1& 1\\1&0\end{pmatrix}=\begin{pmatrix}8& 5\\5&3\end{pmatrix}\\ \end{aligned}\]and it's beginning to look like \[A^n=\begin{pmatrix} F_{n+1}&F_n\\ F_n&F_{n-1}\end{pmatrix}\]
We don't avoid induction altogether this way, because we need it to prove this, but it's an incredibly easy induction because \[\begin{pmatrix} F_{k+1}&F_k\\ F_k&F_{k-1}\end{pmatrix}\begin{pmatrix}1& 1\\1&0\end{pmatrix}=\begin{pmatrix} F_{k+1}+F_k&F_{k+1}\\ F_k+F_{k-1}&F_k\end{pmatrix}=\begin{pmatrix} F_{k+2}&F_{k+1}\\ F_{k+1}&F_k\end{pmatrix}\]
Why is this helpful? Because \(|AB|=|A||B|\) so that
\[\begin{aligned} &\left|A^n\right|=|A|^n\\\phantom{-}\\ \Rightarrow &F_{n+1}^{\;2}-F_nF_{n+2}=(-1)^n \end{aligned}\]Look at that: a kind of magic, it seems to me! See how much easier this is than the direct induction even though we need a bit of matrix knowledge.
Another idea: we can convert what looks like an arithmetic problem into a combinatorics problem, solve this new problem, and then convert the solution back into an arithmetic problem. Here's one way to go about it:
How many numbers with digits only 1 or 2 or have a digit sum 9? We'll call the set of all such numbers \(B_9\) and the size of this set \(b_9\) .
You can put a 1 on the end of a number in \(B_8\) or a 2 on the end of a number in \(B_7\) to get a number in \(B_9\), and every number in \(B_9\) can be created in exactly one of these two ways, so that \[b_9=b_8+b_7\]
Clearly \(b_1=1\) and \(b_2=2\), which means that \(b_n=\text{Fib}_{n+1}=F_{n+1}\).
Now we want to show that, for example, \[F_{10}^2-F_{11} F_9=b_9^{\;2}-b_{10} b_{8}=-1\] which means that \(B_9\times B_9\) must be the same size as \(B_8\times B_{10}\) give or take one element. (Remember that \(S\times T\) is the set of ordered pairs where the first element is in \(S\) and the second is in \(T\).)
What we are looking for is a mapping from \(B_9\times B_9\) to \(B_8\times B_{10}\) which associates every element of \(B_9\times B_9\) with precisely one element of \(B_8\times B_{10}\), leaving one element in \(B_8\times B_{10}\) without a correlate in \(B_9\times B_9\).
Any mapping that satisfies this condition will do, and there are many, many possibilities. All we need to find is one; this one, for example:
Take two numbers in \(B_9\); for example,
\(L=221121 \in B_9\) and \(R=22212\in B_9\)I want to associate an element of \(B_{8}\) with \(L\) and an element of \(B_{10}\) with \(R\). I can do this either by taking one of the \(1\)s from \(L\) and moving it to \(R\) or by taking a \(1\) from \(R\) and swapping it with a \(2\) from \(L\). The only question is, precisely which digit do we move and precisely where to we put it once we've moved it. We need a clear and definite algorithm, and one where there is only one element in \(B_9\times B_9\) that maps onto a particular element of \(B_8\times B_{10}\).
Look for the first \(1\) from the left in the two numbers. It's the third digit in \(L\) and the fourth digit in \(R\), so the very first one is in \(L\). Delete that \(1\) from \(L\) and insert it to make a new third digit in \(R\) to get
\(L'=22121\in B_8\) and \(R'=221212\in B_{10}\)
If, as in this next example, the occurs first in :
then we will take the first \(1\) in \(R\) and swap it with the corresponding \(2\) in \(L\) to get
\(L'=22112\in B_8\) and \(R'=222121\in B_{10}\)
What about \(L=221121 \in B_9\) and \(R=22122\in B_9\)?
We'll treat this like the first type to get
\(L'=22121\in B_8\) and \(R'=221121\in B_{10}\)
and this will apply too if the digits are all \(1\)s. After all, if we think of it as the second type, we won't achieve our goal of generating an element of \(B_8\times B_{10}\).
So this map clearly takes each element of \(B_9\times B_{9}\) to an element of \(B_8\times B_{10}\), but is it one-to-one?
Yes it is! To get back from \((L',\,R')\) to \((L,\,R)\), follow exactly the same algorithm, but switch \(L'\) and \(R'\) before starting, and then switch \(L\) and \(R\) back at the end.
That means that any element of \(B_8\times B_{10}\) can be mapped back to the original element of \(B_9\times B_{9}\), and the map is one-to-one. However, there is one element of \(B_8\times B_{10}\) that has no correlate in \(B_9\times B_{9}\). It's the element \((2222,\;22222)\). That is to say, we cannot reach the pair of numbers \(L'=2222\in B_8\) and \(R'=2222\in B_{10}\) from \(B_9\times B_{9}\).
This means that \[b_8 b_{10}=b_9^{\;2}+1\] as we wanted.
On the other hand, the element \((22222,\;22222)\) in \(B_{10}\times B_{10}\) cannot be mapped by our algorithm to an element of \(B_9\times B_{11}\) but every element in \(B_8\times B_{10}\) can be reached from an element of \(B_{10}\times B_{10}\) so that \[b_9 b_{11}=b_{10}^{\;2}-1\]
The same argument will apply to any value of \(n\), so that when \(n\) is odd, then \(b_{n-1}b_{n+1}=b_n^{\;2}+1\) so that \(F_{n+1}^{\;\;2}-F_nF_{n+2}=-1\)
and when \(n\) is even, \(b_{n}^{\;\;2}=b_{n-1} b_{n+1}+1\) so that \(F_{n+1}^{\;\;2}-F_nF_{n+2}=1\).
Put them together, and \[F_{n+1}^{\;\;2}-F_nF_{n+2}=(-1)^n\] which is Cassini's identity.
This is an example of a proof whose difficulty lies in describing it clearly rather than in the maths itself.
We can look at the same algorithm with pictures using tilings of \(1\times n\) rectangles with \(1\times 1\) and \(1\times 2\) rectangles. Notice that any tiling of a \(1\times 9\) rectangle can be obtained either from a \(1\times 8\) tiling by adding a \(1\times 1\) at the end or from a \(1\times 7\) tiling by adding a \(1\times 2\) at the end. If \(T_n\) is the number of such tilings, then we have
\(T_9=T_8+T_7\) and \(T_1=1,\;T_2=2\) so that \(T_n=\text{Fib}_{n+1}\) as before with \(b_n\).
For example, here is \(L=221121\in B_9\) and \(R=22212\in B_9\) becoming \(L'=22121\in B_8\) and \(R'=221212\in B_{10}\)
Meanwhile, here is \(L=22212\in B_9\) and \(R=221121\in B_9\) becoming \(L'=22112\in B_8\) and \(R'=222121\in B_{10}\)
Now, it's easy to see how to undo the map: going from the bottom diagram to the top, choose the second set of actions if the first single block is above, and the top set of actions if the first single block is below (or they are both the same).
Notice that
cannot be reached from \(B_9\times B_{9}\), while
cannot be mapped by this algorithm to \(B_9\times B_{11}\). These two facts together account for the \((-1)^n\) in Cassini's identity.