# Proofs for an equality

I was working on a little problem and came up with a nice little equality which I am not sure if it is well-known (or) easy to prove (It might end up to be a very trivial one!). I am curious about other ways to prove the equality and hence I thought I would ask here to see if anybody knows any or can think of any. I shall hold off from posting my own answer for a couple of days to invite different possible solutions.

Consider the sequence of functions: \begin{align} g_{n+2}(x) & = g_{n}(x) - \left \lfloor \frac{g_n(x)}{g_{n+1}(x)} \right \rfloor g_{n+1}(x) \end{align} where $x \in [0,1]$ and $g_0(x) = 1, g_1(x) = x$. Then the claim is: $$x = \sum_{n=0}^{\infty} \left \lfloor \frac{g_n}{g_{n+1}} \right \rfloor g_{n+1}^2$$

-

I'll let you decide if it's trivial :-):

\begin{align*} \sum_{n=0}^{\infty} \left \lfloor \frac{g_n}{g_{n+1}} \right \rfloor g_{n+1}^2 &= \sum_{n=0}^{\infty} \left( \left \lfloor \frac{g_n}{g_{n+1}} \right \rfloor g_{n+1} \right) \cdot g_{n+1} \\&= \sum_{n=0}^{\infty} \left( g_{n} - g_{n+2} \right) \cdot g_{n+1} \\&= \sum_{n=0}^{\infty} \left(g_{n} g_{n+1} - g_{n+1} g_{n+2} \right) \\&= g_0 g_1 = x, \end{align*} by a telescopic cancelation.

Technical note: Convergence. The above manipulations are valid only after we check the convergence of the infinite series. Note that $$g_{n+2} = g_{n+1} \cdot \left \{ \frac{g_{n}}{g_{n+1}} \right\} ,$$ where $\{ \cdot \}$ denotes fractional part. Hence, inductively we see that the sequence $(g_n)$ is nonnegative and monotone decreasing; therefore it converges. We claim that $g_n$ in fact converges to $0$. Towards a contradiction, assume that $\lim\limits_{n \to \infty} \ g_n > 0$. Then for large enough $n$, we have $1 < \frac{g_n}{g_{n+1}} < \frac{3}{2}$, and hence $\left\{ \frac{g_n}{g_{n+1}} \right\} < \frac{1}{2}$. Therefore $g_{n+2}\lt \frac{g_{n+1}}{2}$, which is a contradiction to the previous sentence. :) Thus $g_n$ converges to $0$.

Finally, for any $N$, we have $$\left| g_0 g_1 - \sum_{n=0}^{N} (g_n g_{n+1} - g_{n+1} g_{n+2}) \right| = g_{N+1} g_{N+2} \to 0.$$ That is, the series $\sum \limits_{n=0}^{\infty} \left(g_{n} g_{n+1} - g_{n+1} g_{n+2} \right)$ converges to $g_0 g_1$ as desired.

-
I feel a bit stupid now ! Thanks – user17762 Dec 18 '11 at 0:21
@Sivaram You're welcome. – Srivatsan Dec 18 '11 at 0:23
I got the equality from a geometric argument and hence I thought this was something nice. :) In the end it turned out to be the most simplest one! – user17762 Dec 18 '11 at 0:26
+1 for clear, concise explanation. – scraimer Dec 18 '11 at 6:08

For whatever it is worth, below is an explanation on why I was interested in this equality. Consider a rectangle of size $x \times 1$, where $x < 1$. I was interested in covering this rectangle with squares of maximum size whenever possible (i.e. in a greedy sense).

To start off, we can have $\displaystyle \left \lfloor \frac{1}{x} \right \rfloor$ squares of size $x \times x$. Area covered by these squares is $\displaystyle \left \lfloor \frac{1}{x} \right \rfloor x^2$.

Now we will then be left with a rectangle of size $\left(1 - \left \lfloor \frac1x \right \rfloor x \right) \times x$.

We can now cover this rectangle with squares of size $\left(1 - \left \lfloor \frac1x \right \rfloor x \right) \times \left(1 - \left \lfloor \frac1x \right \rfloor x \right)$.

The number of such squares possible is $\displaystyle \left \lfloor \frac{x}{\left(1 - \left \lfloor \frac1x \right \rfloor x \right)} \right \rfloor$.

The area covered by these squares is now $\displaystyle \left \lfloor \frac{x}{\left(1 - \left \lfloor \frac1x \right \rfloor x \right)} \right \rfloor \left(1 - \left \lfloor \frac1x \right \rfloor x \right)^2$.

And so on.

Hence, at $n^{th}$ stage if the sides are given by $g_{n-1}(x)$ and $g_n(x)$ with $g_n(x) \leq g_{n-1}(x)$, the number of squares with side $g_{n}(x)$ which can be placed in the rectangle of size $g_{n-1}(x) \times g_n(x)$, is given by $\displaystyle \left \lfloor \frac{g_{n-1}(x)}{g_{n}(x)} \right \rfloor$.

These squares cover an area of $\displaystyle \left \lfloor \frac{g_{n-1}(x)}{g_{n}(x)} \right \rfloor g^2_{n}(x)$.

Hence, at the $n^{th}$ stage using squares we cover an area of $\displaystyle \left \lfloor \frac{g_{n-1}(x)}{g_{n}(x)} \right \rfloor g^2_{n}(x)$.

The rectangle at the $(n+1)^{th}$ stage is then given by $g_{n}(x) \times g_{n+1}(x)$ where $g_{n+1}(x)$ is given by $g_{n-1}(x) - \left \lfloor \frac{g_{n-1}(x)}{g_n(x)} \right \rfloor g_n(x)$.

These squares end up covering the entire rectangle and hence the area of all these squares equals the area of the rectangle.

This hence gives us $$x = x \times 1 = \sum_{n=1}^{\infty} \left \lfloor \frac{g_{n-1}(x)}{g_{n}(x)} \right \rfloor g^2_{n}(x)$$

When I posted this question, I failed to see the simple proof which Srivatsan had.

-
+1 I like this motivation. =) – Srivatsan Dec 19 '11 at 4:43