Sometimes it is feasible to visualize the simplification of an expression by means of a picture.
As an example we choose the expression 1 + 3 + 5 + 7 + ... + (2n-1).
Count the number of squares in the distinctive colors.
The picture inmediately reveals 1 + 3 + 5 + 7 + ... + (2n-1) = n2.
Let us consider an example with Fibonacci numbers: g2,n = F12 + F22 + F32 + ... + Fn2
We are looking for an expression for g2,n:
Put a square with length (= width) = F1 against a square with length F2,
then this forms a rectangle with width F2 and length F3 (or F12 + F22 = F2F3).
Now put next to this rectangle a square with length F3 so, that there emerges a rectangle with width F3 and length F4 (or F12 + F22 + F32 = F3F4).
Continue this process. This shows that g2,n = FnFn+1
The same picture also reveals a formula for g1,n = F1 + F2 + F3 + ... + Fn.
Tip: Count together the lengths of the sides, that adjoin the left side or the top of the 5 subfigures.
You can find another example in The sequence of Perrin.
Paths
In the introduction we have examined the number of ways in which a row of stones can be put
side by side to form a path of length n (and width 1) using square stones with length 1 and rectangular ones width width 1 and length 2.
This could be done in Fn+1 ways.
We can use the construction of paths to simplify sums like g1,n = F1 + F2 + F3 + ... + Fn or g2,n = F12 + F22 + F32 + ... + Fn2
.
Let us start with an expression for g1,n
In the path problem of the introduction we can ask ourselves:
Where is the last 1x2 stone put?
If this stone occupies the i-th and the i+1-st place,
then the preceding part of the path can be laid in Fi ways.
The index i can vary between 1 and n-1. So, we can express the total number of paths (patterns) in two ways: Fn+1 = F1 + F2 + F3 + ... + Fn-1 + 1.
The last term 1 stems from the circumstance that it is possible that there are no rectangular stones used.
Thus g1,n = Fn+2 - 1
We will now try to find an expression for g2,n.
We will anew make use of the path problem from the introduction:
Lay 2 parallel paths.
In the left path we leave out the last n-th spot.
The number of paths (pattern) is FnFn+1.
On what spot is the last square stone put?
For that, only the following spots are feasible:
On the n-th spot of the left path; on the n-1-st spot of the left path; on the n-2-nd spot of the right path;
on the n-3-rd spot of the left path, etc.
Suppose, that the last square stone is put on the i-th spot,
then the remaining part (before the i-th spot)
in both paths can be put in Fi ways, thus on the whole in Fi2 ways.
Consequently, we find, by examining all possible values of i, that
FnFn+1 = F12 + F22 + ... + Fn2
