Add Me!Close Menu Navigation

Square Sequence

The sequence f_1, f_2, \cdots satisfies

    $$ f_{m+n} + f_{m - n} = \frac{f_{2m} + f_{2n}}{2}$$

for all nonnegative integers n,m and m \ge n. If f_1 = 1, determine f_n

1. The sad shit

Everytime I see problems. like. this., I just go like “oh fuck.” And it’s for good reasons too, because there are usually very few “techniques” in general that can be used to solve generic functional equations. Anyways, enough with the sad shit, let’s move on

2. Moving on…

We first probe the system for some general properties. We know that f_1 = 1, but as the problem suggests, we should check out what f_0 is.

Finding f_0

Your first impulse may be to set n=0, let’s skip that for now. Instead, we look at the case of n=m

    \begin{align*} f_{m+m} + f_{m-m} &= \frac{f_{2m} + f_{2m}}{2} \\ f_{2m} + f_0 &= f_{2m} \\ f_0 &= 0 \end{align*}

That’s just great.

Finding f_2

Now that we’re rolling, let’s probe the system a little further. Setting m = 1, n = 0, we see that

    \begin{align*} f_1 + f_1 &= \frac{f_2 + f_0}{2} \\ 4f_1 &= f_2 \\ f_2 &= 4 \end{align*}

In fact, this seems to suggest an interesting property about f_n \sim f_{2n}.

Show that f_{2n} = 4 f_n

This can be easily shown by construction. Set m=m and n=0, our equation becomes

    \begin{align*} f_{m} + f_m &= \frac{f_{2m} + f_0}{2} \\ 4f_m &= f_{2m} + 0 \\ f_{2m} &= 4f_m\ \square \end{align*}

Awesome, let’s generate some more numbers from what we have

    \[\begin{tabular}{c|c|c|c|c|c} n & 1 & 2 & 4 & 8 & 16 \\ \hline $f_n$ & 1 & 4 & 16 & 64 & 256 \end{tabular}\]

Hmm, seems like for n = 2^x, f_n = 4^x = n^2, but we don’t have a good spread on the generated numbers yet, so let’s keep on going.

Show that f_{m+n} + f_{m-n} = 2(f_m + f_n)

This extends directly from f_{2n} = 4f_n \implies \frac{f_{2m} + f_{2n}}{2} = 2(f_m + f_n). \blacksquare

Finding f_3

Since we only know f_0,f_1,f_2, we can only generate f_3 in terms of these known terms. We observe that for m+n=3,m-n=1, this satisfies our criterion. Set m=2, n=1

    \begin{align*} f_{2+1} + f_{2-1} &= 2(f_2 + f_1) \\ f_3 + f_1 &= 2(f_2 + f_1) \\ f_3 &= 2(f_2 + f_1) - f_1 \\ &= 2(4+1)-1 \\ &= 9 \end{align*}

Interestingly enough, this fits in with the previous observation that for n = 2^x, f_n = n^2. Let’s make one last probe at the system to be sure.

Finding f_5

We’ve already generated f_4 from the generating class of f_1,f_2,f_4,\cdots so we now turn our attention to finding f_5 using only f_1,f_2,f_3,f_4. Again, we observe that m+n=5,m-n=3,m=4,n=1 satisfies this property.

    \begin{align*} f_{4+1} + f_{4-1} &= 2(f_4 + f_1) \\ f_5 + f_3 &= 2(f_4 + f_1) \\ f_5 &= 2(f_4 + f_1) - f_3 \\ &= 2(16+1)-1 \\ &= 25 \end{align*}

Whelp, that’s good enough for me. Let’s buckle down and prove once and for all that f_n = n^2; but first, we derive an even more general recurrence that exhibits trivial monotone properties in its indices that is suitable for inductive proofs. We apply the observations made from finding f_3 and f_5.

Show that f_{n+1} = 2(f_n + 1) - f_{n-1}

As per f_3 and f_5, set n=1

    \begin{align*} f_{m+1} + f_{m-1} &= 2(f_m + f_1) \\ &= 2(f_m + 1)\\ f_{m+1} &= 2(f_m + 1)- f_{m-1}\ \square \end{align*}

3. Show that f_n = n^2

We will show this inductively on the naturals n. Informally, we will use the identity f_{n+1} + f_{n-1} = 2(f_n + 1) to form the foundation of the inductive steps.

Suppose P_n \equiv f_n = n^2, as we’ve already established, P_1, P_2, P_3, P_4, P_5, we now outline the inductive steps.

Show that P_{n-1},P_n \implies P_{n+1}

    \begin{align*} f_{n+1} &= 2(f_n + 1) - f_{n-1} &\tiny{\mbox{Discharge $P{n},P_{n-1}$}} \\ &= 2(n^2 + 1) - (n-1)^2 \\ &= 2n^2 + 2 - n^2 + 2n - 1 \\ &= n^2 + 2n + 1 \\ &= (n+1)^2 \\ &\implies P_{n+1} \end{align*}

This concludes our proof that f_n = n^2. \blacksquare

Posted By Lee

Woosh