Square Hunch

Let $a_0, a_1, a_2, …$ be a sequence of integers, where $a_{m+n} + a_{m-n} = ½(a_{2m}+a_{2n})$. If $a_1 = 1$, what would be the value of $a_{1997}$?¹

The first thing one should do when trying to tackle something like this is to “check out the terrain”. I would be very tempted to write a computer program to find the values for me right away, but where should the program start from, considering that this is a recurrence? We do know how to implement recursive functions, but the way the recurrence is formulated, it’s not straightfoward to define it.

Release the mathematician in you

Let’s try to tackle this problem analitically and without computer aid. Where to begin? What about trying to establish a kind of ground truth?

Step 1. Check out the terrain

Let $m = 0$, $n = 0$, then:

Great, we now have two data points: $a_0$ and $a_1$. Can we try and generalize the equation?

Step 2. Find the general equivalence for some fixed values

Assuming we fix $n = 0$, the recurrence becomes:

This equation² is neat for two things: (i) it no longer depends on two variables ($n$ and $m$), and thus can provide a solution given the exact index we want to compute; and (ii) if we multiply the current value by 4, we get the solution for the current index $\times$ 2.

With this result in mind, let’s calculate a few more values:

Step 3. Fill some holes to get a clear picture

As we’ve already gathered some solutions, let’s attempt to calculate $a_3$. Let $m = 2$, $n = 1$, then:

… wait a minute.

Step 4. Establish an hypothesis

Could it be that $\class{bghighlight}{H(a_k = k^2)}$? If so, then $a_5 \stackrel{?}{=} 25$. Shall we try it out? Let $m = 4$, $n = 1$, then:

Hurray! We now know a lot more about the recurrence:

Step 5. Prove it!

Yeah, yeah… by now most of us would be convinced that we reached an easy solution to get us to $a_{1997}$, but how can we be certain that our hypothesis will not fail with larger numbers? Well, we must prove it… And prove it we will!

Step 5.1. Choose a proof approach

Think about it… We are trying to prove sequences, and we already know some lower values of the sequence. We want to prove that our hypothesis is valid for every element of the sequence. This smells a lot like induction, particularly strong induction.

In strong induction we assume that when attempting to prove an hypothesis $H$, then:

… in other words, if the inductive hypothesis holds for all values up to $k$, starting from a base value $k_0$, then it must hold for $k+1$.

Step 5.2. Induction it is! Test the base case

Does $H(k = 0)$ hold? Yep, since $0^2 = 0 = a_0$. We also know that for $H(k = 1) ≡ 1^2 = 1 = a_1$, and for $H(k = 2) ≡ 2^2 = 4 = a_2$, so although unecessary, it boosts our confidence.

Step 5.3. Demonstrate the inductive step

Now we assume that, since our hypothesis hold for $k = 0, 1, 2, …, x$ it must hold for $k = x+1$:

$a_{x+1} + a_{x-1} = \frac{1}{2}(a_{2x}+a_{2\times 1})$
$≡$ { since $4a_m = a_{2m}$ }
$a_{x+1} + a_{x-1} = \frac{1}{2}(4a_{x}+a_{2})$
$≡$ { given that $a_k = k^2$ }
$a_{x+1} + (x-1)^2 = \frac{1}{2}(4x^2+a_{2})$
$≡$ { knowing that $a_2 = 4$ }
$a_{x+1} + (x-1)^2 = 2x^2+2$
$≡$ { since $(a-b)^2 = (a^2-2ab+b^2)$ }
$a_{x+1} = 2x^2+2 - (x^2-2x+1)$
$≡$ { simplifying }
$a_{x+1} = x^2+2x+1$
$≡$ { since $(a+b)^2 = (a^2+2ab+b^2)$ }
$a_{x+1} = (x+1)^2$
$≡$ { let $k=x+1$ }
$\class{bghighlight}{a_k = k^2}$ Q.E.D.

Step 6. Pown that puzzle!

$\class{bghighlight}{a_{1997} = 1997^2 = 3988009}$. Easy, uh?