Solve a recurrence relation in two variables

Question

Suppose the function $f : \mathbb{N}\to\mathbb{N}$ is such that $f(1)=1$ and $$f(2m) + f(2n) = 2(f(m+n) + f(m-n))$$ for all $m>n>0$. I would like to show that this implies $f(n) = n^2$ for all $n\in\mathbb{N}$.

It is easy to show that $f(n)=n^2$ is a solution, just by substituting, but I'm having trouble proving uniqueness. I know about mathematical induction but in this case, the fact that there are two variables $m$ and $n$ is giving me trouble. Any help appreciated.

Added: the part that's giving me trouble is that I cannot assume that $f(0)$ exists. If I could assume that, then $f(0)=0$ by putting $m=n=0$, and then by putting $m=n$ I could show that $f(2m) = 4f(m)$, from which it's not hard to continue.

I guess my question is: am I allowed to extend $f$ by defining $f(0)=0$, and use that in my reasoning? It seems like cheating somehow.

Answer 1

I'm not quite satisfied with this solution, but it's the best I can come up with. All my approaches ultimately depend on finding initial values like $f(2), f(3), f(4)$, for which I had no motivating approach other than trying numerous cases and hoping it eventually works out.

---

The following 2 equations are the most important that we'd use:

Calculating powers of 2 from smaller powers of 2: $$f(2^{k+1} ) + f(2^k) = 2 f(3\times 2^{k-1}) + 2 f( 2^{k-1} ) = 4 f(2^k) + 4 f( 2^{k-1} )$$

Calculating multiples of $2^{k-a}$ from multiples of $2^{k-a+1}$:
Where $O$ is an odd number,
$$f( \frac{O+1}{2} \times 2^{k-a+1}) + f( \frac{O-1}{2} \times 2^{k-a+1}) =2 f( O \times 2^{k-a} ) + f( 2^{k-a} ).$$

Claim 1: Let $ f(2) = a, f(4) = b$. Then, the rest of the values could be determined from these unknowns.

Proof of claim 1: We do so by induction, showing that we can determine the values from $f(2^k+1)$ to $f(2^{k+1})$.
We use the first equation to get $2^{k+2}$, then use the second equation to calculate the odd multiples of $2^{k}$ less than $2^{k+2}$, then calculate the odd multiples of $2^{k-1}$ less than $2^{k+2}$, then calculate the odd multiples of $2^{k-2}$ less than $2^{k+2}$, so on and so forth. $_\square$

Note: While we have determined these values through the equations, we still have to ensure that the all of the equations hold in general. It is by verifying these equations that we get more information.

Claim 2: We can show that $f(4) = 3f(2) + 4$, and that $f(2) = 4$.

Corollary: With $f(1) = 1, f(2) = 4, f(4) = 16$, we can repeat the induction at the start (once again working with the powers of 2 then multiples of $2^{k-a}$) and prove that $f(n) = n^2$.
Finally, verify that with $ f(n) = n^2$, both equations hold in all generality. So this is indeed a solution.

Proof of Claim 2: We can list out some of the these values, with the sequence obtained via the above algorithm:

$f(1) = 1$
$f(2) = a$
$f(4) = b$
$f(3) = (a+b-2) / 2 $
$f(8) = 4a+3b$
$f(6) = a+2b$
$f(5) = (a+3b-2) /2$
$f(7) = (5a+5b-2)/2$

With $ f(8) + f(2) = 2f(5) + 2f(3)$, we get that $ b = 3a + 4$. Rewriting the above list, we have
$f(1) = 1$
$f(2) = a$
$f(3) = 2a+1$
$f(4) = 3a + 4$
$f(5) = 5a + 5$
$f(6) = 7a+8$
$f(7) = 10a + 9$
$f(8) = 13a + 12$

There seems to be nothing further we can do, so let's generate more values.

$f(16) = 51a+52$
$f(12) = 29a + 28$
$f(10) = 20a+20$
$f(9) = (33a+30) / 2$
(I skipped listing out the rest)

With $f(16) + f(2) = 2 f(9) + 2 f(7) $, we get that $ a = 4$.
(With this value, you can check that the listed ones work out to $f(n) = n^2$.)$_\square$

Answer 2

Ok, I try to explain completely my idea.

First, taking $n=1$, $n=2$, $m\geq 3$, eliminating $f(2m)$, we obtain that

$$f(m+2)-f(m+1)-f(m-1)+f(m-2)=(f(4)-f(2))/2 $$ and we put $d=(f(4)-f(2))/2$. This is a linear recurrence equation; we solve it completely, we do not care about particular values of $f(m)$ for the moment. The general solution is of the form (particular solution+general solution of the homogeneous equation).

We try to find a particular solution of the form $cm^2$, and we find $cm^2$, with $c=d/6$.

Now the homogeneous equation ; the polynomial characteristic of the recurrence is $(x-1)^2(x^2+x+1)$, with a double root $1$, and simple roots $j$, $j^2$ (notation for the cubic roots of unity). So the general solution of the homogeneous recurrence equation is of the form $u+vm+wj^{m}+qj^{2m}$ for some constants $u,v,w,q$. (note that for example, $j^m+j^{2m}$ is in $\mathbb{R}$, and a solution of the homogeneous recurrence equation ; we cannot, at this point, eliminate these terms).

So, what we have proven is that a solution of the original equation is of the form

$$f(m)=cm^2+u+vm+wj^{m}+qj^{2m}$$ Now we replace in the original equation:

$$4cm^2+u+2mv+wj^{2m}+qj^{4m}+4cn^2+u+2nv+wj^{2n}+qj^{4n}$$ is equal to $$2[c(m+n)^2+u+v(m+n)+wj^{m+n}+qj^{2(m+n)}+c(m-n)^2+u+v(m-n)+wj^{m-n}+qj^{2(m-n)}]$$

Now the expression of a recurrence sequence (here we fix $n$, and $m$ is the variable) as $\sum\alpha \beta^m$ is unique. So we look at the coefficients of $1,m,m^2, j^m, j^{2m}$. The coefficient of $m$ on the first side is $2v$; on the second side, $4v$. Hence $v=0$. The coefficient of $j^{m}$ on the first side is $q$, on the second side $2w(j^n+ j^{-n})$, hence $q=2w(j^n+ j^{-n})$; the coefficients of $j^{2m}$ give also $w=2q(j^{2n}+j^{-2n})$; choosing $n=3$ gives $q=w=0$. The constant coefficient is (using $v=w=q=0$) $2u+4cn^2$ in the first expression,and $4u+4cn^2$ in the second, hence we get $u=0$, and we have proven that a solution of the original equation must be of the form $c m^2$ for some constant $c$. It is easy to finish.