1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is there a typo? Is it $f(m+n)+f(m-n)$? You typed $f(m+n)+m-n$. $\endgroup$ – Yip Jung Hon May 31 at 14:21
  • 1
    $\begingroup$ 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... $\endgroup$ – R.J. Etienne May 31 at 14:32
  • $\begingroup$ yes sorry im fixing it now $\endgroup$ – ahmed May 31 at 14:38
  • 1
    $\begingroup$ 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 $\endgroup$ – Yip Jung Hon May 31 at 15:52
  • 1
    $\begingroup$ 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. $\endgroup$ – QC_QAOA May 31 at 16:47
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ wow, I need some time to read & hopefully understand ^^ thanks for the answer $\endgroup$ – ahmed May 31 at 16:56
  • $\begingroup$ 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)\}$. $\endgroup$ – Ivan Neretin May 31 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.