# Finding general term of sequence satisfying $f(m+n)+f(m-n)=\frac 12(f(2n) + f(2m))$ and $f(1) = 1$

The problem asks to compute $$f(2020)$$ knowing that

$$f(1) = 1$$ and $$f(m+n)+f(m-n)=\dfrac 12(f(2n) + f(2m))$$ for integers $$m,n$$ such that $$m>n\ge 1$$.

My try :

I conjectured $$f(n) = kn^2$$ where $$k$$ is a random constant which has to be $$1$$ due to $$f(1) = 1$$

I plugged different values in $$n$$ and $$m$$ trying to prove this by induction but in vain.

it seem there is something missing.

• Is there a typo? Is it $f(m+n)+f(m-n)$? You typed $f(m+n)+m-n$. – Yip Jung Hon May 31 at 14:21
• Are $m,n$ integers? Is it $f(m+n)+f(m-n)$ or $f(m+n)+m-n$? How would you calculate $f(2)$ and $f(3)$? Something seems to be wrong in your statement... – R.J. Etienne May 31 at 14:32
• yes sorry im fixing it now – ahmed May 31 at 14:38
• I realised I made a mistake in my answer, so I'm deleting it for now. I'll try the problem again tomorrow. Though it doesn't seem to hard via induction – Yip Jung Hon May 31 at 15:52
• There is no unique answer as your system has $3$ degrees of freedom. That is, you need $3$ initial conditions in order to have a unique solution. – QC_QAOA May 31 at 16:47

There is no unique answer but assumptions can be made that give a unique answer. Suppose $$f(x)$$ can be written in the form

$$f(x)=\sum_{i=0}^\infty a_i x^i$$

where $$a_i$$ are constants that could be zero. Then

$$0=2f(m+n)+2f(m-n)-f(2m)-f(2m)$$

$$=2\sum_{i=0}^\infty a_i\left(\sum_{j=0}^i\binom{i}{j}n^jm^{i-j}\right)+2\sum_{i=0}^\infty a_i\left(\sum_{j=0}^i\binom{i}{j}(-1)^jn^jm^{i-j}\right)$$

$$-\sum_{i=0}^\infty a_i2^in^i-\sum_{i=0}^\infty a_i 2^i m^i$$

$$=a_0(3-n^2)+a_1(2m-2n^2)+a_2*0+a_3(-4m^3-8n^2+12mn^2)+\cdots$$

It is useful for us to examine this expression at $$m=n^3$$. Then it becomes

$$0=2\sum_{i=0}^\infty a_i\left(\sum_{j=0}^i\binom{i}{j}n^{3i-2j}\right)+2\sum_{i=0}^\infty a_i\left(\sum_{j=0}^i\binom{i}{j}(-1)^jn^{3i-2j}\right)$$

$$-\sum_{i=0}^\infty a_i2^in^i-\sum_{i=0}^\infty a_i 2^i n^{3i}$$

$$=a_0(3-n^2)+a_1(-2n^2+2n^3)+a_2*0+a_3(-8n^2+12n^5-4n^9)+\cdots$$

Basically, we will show that for $$i\geq 3$$, the coefficient on $$a_i$$ is a polynomial of $$n$$ with degree $$n^{3i}$$. Now that we know what to look for, this is easy to see. For any $$i$$, the highest power of $$n$$ in the coefficient of $$a_i$$ will be

$$2\binom{i}{0}n^{3i-2*0}+2\binom{i}{0}(-1)^0n^{3i-2*0}-2^in^{3i}=2n^{3i}+2n^{3i}-2^in^{3i}=-(2^i-4)n^{3i}$$

For $$i\geq 3$$, this will always be nonzero. In order to make the next part clear, denote these polynomials in front of $$a_i$$ by $$p_i$$ and define $$M_i-1$$ to be the maximum coefficient (in terms of absolute value) in the polynomials in the set $$\{p_0,p_1,\dots,p_i\}$$. Further, define $$A_i$$ to be $$\max\{|a_0|,|a_1|,\dots,|a_i|\}$$. Then we know

$$\sum_{j=0}^i a_j p_j\leq \sum_{j=0}^i |a_j p_j|\leq \sum_{j=1}^i A_i M_i n^{3j}+A_iM_in^2=A_i M_i\left[ \frac{n^{3i+3}-n^3}{n^3-1}+n^2\right]$$

But this implies

$$\lim_{n\to\infty}\frac{A_i M_i\left[ \frac{n^{3i+3}-n^3}{n^3-1}+n^2\right]}{p_{i+1}}=\lim_{n\to\infty}A_iM_i \frac{1}{n^3-1}=0$$

We conclude that for all $$i\geq 3$$, there exists an $$N$$ such that $$n\geq N$$ implies

$$\left|\sum_{j=0}^i a_j p_j\right|<|a_{i+1}p_{i+1}|$$

We can manually check that this condition also holds for $$i=0$$ and $$i=2$$. Of course, this implies that all the coefficients $$a_i$$ must be zero (else the expression would not be zero as $$n$$ goes to infinity). However, there is one exception: $$p_2=0$$ which means that $$a_2$$ is in fact a free variable. That is

$$f(x)=a_2x^2$$

From the initial condition, we conclude $$f(x)=x^2$$. Of course, all of this followed from the assumption that $$f(x)$$ could be expanded as a (possibly) infinite polynomial. There is not a nice, unique solution if you do not use this assumption. In fact, a whole infinite family of solutions can be constructed quite easily. That is, your solution is uniquely determined by the set $$\{f(1),f(2),f(3)\}$$. I will now prove this by strong induction:

Set $$m=2$$ and $$n=1$$. Then

$$f(4)=f(2m)=-f(2n)+2f(m+n)+2f(m-n)=-f(2)+2f(3)+2f(1)$$

Now, assume we are able to construct $$\{f(1),f(2),\dots,f(N)\}$$ using a linear combination of $$\{f(1),f(2),f(3)\}$$ (where $$N$$ is an even number greater than or equal to $$4$$). If we can show how to construct $$f(N+1)$$ and $$f(N+2)$$, using a linear combination of this set, then we are done. This is easily done by first choosing: $$m=\frac{N+2}{2}$$ and $$n=1$$. Then

$$f(N+2)=f(2m)=-f(2n)+2f(m+n)+2f(m-n)$$

$$=-f(2)+2f\left(\frac{N+2}{2}+1\right)+2f\left(\frac{N+2}{2}-1\right)$$

Note that each of these is a linear combination of our set (we assumed this by strong induction) as

$$\frac{N+2}{2}+1=\frac{N}{2}+2\leq N$$

(as $$N\geq 4$$). For $$f(N+1)$$, let $$m=\frac{N+2}{2}$$ and $$n=\frac{N}{2}$$. Then

$$2f(N+1)=2f(m+n)=f(2m)+f(2n)-2f(m-n)=f(N+2)+f(N)-2f(1)$$

$$f(N+1)=\frac{1}{2}f(N+2)+\frac{1}{2}f(N)-f(1)$$

However, we know all of these can be made as a linear combination of our set. We just showed that $$f(N+2)$$ can be constructed and we assumed $$f(N)$$ could be by induction. Thus, every $$f(n)$$ can be constructed from the set $$\{f(1),f(2),f(3)\}$$. For example, if

$$\{f(1),f(2),f(3)\}=\{1,4,9\}$$

then $$f(x)=x^2$$ and $$f(2020)=2020^2=4080400$$. However, if

$$\{f(1),f(2),f(3)\}=\{1,2,3\}$$

then

$$f(n)=\{1,2,3,6,9,14,17\}\text{ and }f(2020)=1442866$$

If we stick with the set $$\{f(1),f(2),f(3)\}$$, then it will always be the case that

$$f(2020)=335483 f(1)-211383 f(2)+510050 f(3)$$

Of course, any three initial conditions will produce a unique solution to your functional equation. That is, if you are given

$$\{f(n_1),f(n_2),f(n_3)\}$$

then it is possible to back out $$f(x)$$ for any value of $$x$$. This is apparent as

$$f(n_1)=a_1 f(1)+b_1f(2)+c_1 f(3)$$

$$f(n_2)=a_2 f(1)+b_2f(2)+c_2 f(3)$$

$$f(n_2)=a_3 f(1)+b_3f(2)+c_3 f(3)$$

(we just showed this by strong induction). Rearranging and solving for $$\{f(1),f(2),f(3)\}$$ will give the desired result. Is this system ever unsolvable? Well that depends if

$$\begin{vmatrix} a_1 & b_1 & c_1\\ a_2 & b_2 & c_2\\ a_3 & b_3 & c_3 \end{vmatrix}$$

can ever be equal to zero. I do not have a proof, but I believe that it should be possible to show by induction that this is always non-zero. If this were the case, the the functional equation would be completely determined by any three initial values.

• wow, I need some time to read & hopefully understand ^^ thanks for the answer – ahmed May 31 at 16:56
• Let's pretend the first half of your answer is just not there, and concentrate on the second one. Now see, using some other combinations of $\{m,n\}$ you might or might not obtain some conditions on $\{f(1),f(2),f(3)\}$. – Ivan Neretin May 31 at 19:06