Evolving Polynomial

On the Cartesian field, each lattice point $(x,y)$ is initially assigned the number $x^2+y^2-1$.

At each step, if $A(x,y)$ represents the number on $(x,y)$, that number is increased by: $$\frac{(x-y) \left( A(x+1,y) + A(x,y-1) - A(x-1,y) - A(x,y+1) \right)}{4}$$

All the additions are done simultaneously.

1. Prove that the numbers at each point are always integers

2. Prove that, aside from the initial configuration, there is never a number that is divisible by 3

Solution

The recursion formula guarantees that $A(x,y)$ is always a polynomial in $x,y$, with real coefficients. In the initial configuration, $B(x,y) = A(x,y) + 1 = x^2+y^2$ is homogeneous in $x,y$ with degree 2. That is, $B(kx,ky) = k^2 A(x,y)$. We will show that this homogeneity is maintained by the recursion formula, and therefore will hold true at all times.

Suppose $A(x,y) = P.x^2 + Q.xy + R.y^2 - 1$ for some real numbers $P,Q,R$ then the recursion formula maintains it. This is because $A(x+1,y) - A(x-1,y)$ cancels out the $x^2,xy,y^2,1$ terms, so only $x,y$ terms are left. Similarly $A(x,y+1) - A(x,y-1)$ will also only preserve $x,y$ terms. So the second factor is homogenous with degree 1, but the factor $(x-y)$ is also homogenous with degree 1, so the added number is homogeneous with degree 2. Therefore, the final number is still of the form $A(x,y) = P'.x^2 + Q'.xy + R'.y^2 - 1$ (for some $P',Q',R'$ constants that may be different from the previous iteration).

Now we also notice that $A(x,y) = A(y,x)$ for all time. This property is preserved in the beginning, but also preserved by the recursion, so the numbers are symmetric with respect to $x,y$. Therefore $P = R$.

Next, we notice that for $x=y$, the additions are always zeros, so $A(x,x) = 2x^2-1$ for all time. Therefore $A(x,x) = (2P+Q)x^2-1 = 2x^2-1$ so $2P+Q = 2$.

This means that, because $Q = 2- 2P$, $A(x,y) = Px^2 + (2-2P)xy + Py^2 - 1= (x^2+y^2 - 1) + (P-1)(x-y)^2$ for some $P$ real (not necessarily integer) that depends on $t$. So we've shown that $A(x,y)$ has the form $(x^2+y^2-1) + K_t(x-y)^2$ for some $K_t$, where $K_0 = 0$.

Then, plugging in to the original recursion formula, we can see: $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +K_t(2(x-y+1)^2 -2(x-y-1)^2))$$ $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +8K_t(x-y))$$ $$K_{t+1} = 3K_t + 1$$ From there, it's a simple matter to see that $K_t = \frac{3^t-1}{2}$ because $K_0 = 0$, but we didn't need to solve the recursion. The fact that $K_0 = 0$ is enough to prove that $K_t$ is always an integer, and that, except for $t=0$, it's always $\equiv 1 \mod 3$.

Because $K_t$ is always an integer then $A(x,y)$ is also integral everywhere. And because $K_t \equiv 1 \mod 3$ then we can check that for any combinations of $x,y \mod 3$, $A(x,y)$ will never be $\equiv 0 \mod 3$.

ODE discrete version

If $f$ is a function that is defined over natural numbers ($f:N \to R$), let $f^*$ denote the function $f^*(n) = f(n) - f(n-1)$. Find all functions such that $$n(f^*)^*(n) + (n-1)f^*(n) = f(n)$$ for all $n > 2$

Solution We can check that $f(n) = A(n-1) + B/2^n$ for any constant $A,B$ satisfies the given equation. Now we show that there's nothing else.

Define $g = f^*+f$. The equation is identical to: $$n(f^*+f)^*(n) =(f^*+f)(n)$$ $$ n(g(n) - g(n-1)) = ng^*(n) = g(n)$$ $$\frac{g(n)}{n} = \frac{g(n-1)}{n-1}$$ for all $n>2$, therefore $g(n)/n$ must be a constant. Remember that $g(1)$ is not defined because $f$ is only defined for $n \geq 1$ thus $g$ is only defined for $n \geq 2$. Furthermore, the value $g(2)$ depends on $f(1)$ and $f(2)$.

Case 1: $g(2) = 0$ In this case then $g(n) = 0 \forall n$. $$(f^*+f)(n) = 0$$ $$f(n) = f(n-1)/2$$ so we easily get $f(n) = k/2^n$ for some constant $k$.

Case 1: $g(2) \neq 0$ Note that if $f$ is a solution to the problem then $kf$ is also a solution to the problem, for all $k$ real numbers. If we replace $f$ by $kf$, then $g$ is also replaced by $kg$. So WLOG, we may assume that $g(2) = 2$

Because $g(n) / n$ is a constant then $$g(n) / n = g(2) / 2 = 1$$ so $g(n) = n \forall n >2$ $$f(n) = \frac{f(n-1) + n}{2}$$ for all $n > 2$.

Because $g(2) = 2 = 2f(2) - f(1)$ then $f(2) = 1+ f(1)/2$ Now notice this pattern: $$f(3) = \frac{f(2) + 3}{2} = 2 + f(1)/4$$ $$f(4) = \frac{f(3) + 4}{2} = 3 + f(1)/8$$ Easy to prove by induction that $f(n) = n-1 + f(1)2^{1-n}$.

From the two cases above, it's clear that any solution of the equation must be in the form of $f(n) = A(n-1) + B/2^n$ for any constant $A,B$

Simplifying Series

Let $a_n = \binom{2n}{n}$ and $b_n = \binom{3n}{n}$. Find a more compact expression for:

$A(x) = a_0 + a_1x + a_2x^2 +\cdots + a_nx^n + \cdots$

$B(x) = b_0 + b_1x + b_2x^2 +\cdots + b_nx^n + \cdots$