Polynomial Recursion

Let us take $g_k$ to be a general polynomial, and thus write it as,

$g_k = \sum_{i=0}^n ( a_i \cdot x^i )$ ( Where n is the degree... some number )

So, putting this in the given recursive relation, and also noticing that in,

$g_{k-1} (x \cdot ( x + 2 ) )$ ,

we cannot get coefficients of $x^2$ anywhere except in

$(x \cdot ( x + 2 ) ) ^2 and (x \cdot ( x + 2 ) ).$

Let $A_k$ be the coefficient of $x^2$ and $B_k$ be the coefficient of x. We get a recursive relation for the coefficients as,

$A_k = (3 \cdot A_{k-1} ) + B_{k-1}$

$B_k = B_{k-1}$ (Thus $B_k = B_0$ for all k) Solving this recurrence relation will give us, $A_k = (3^k -1)/2$ . This can be obtained by repeatedly substituting it in the relation(Short way) or by some other prevalent methods.

Now , putting k=299 we just have to find the remainder with 1000, which can be easily done using binomial. Writing $3^{299}$ as $3 * ((10-1)^{149})$ . We leave the terms with 1000 as a factor alone and get the answer as 333.

Consider the recursive polynomials $g_{k}(x)$ ,

$g_{0}(x)$ = $x$ and $g_{k+1}(x)$ = $g_{k}(x^{2}$ $+$ $2x)$ $-$ $g_{k}(x)$

Thus,

$g_{1}(x)$

= $x^{2}$ $+$ $2x$ $-$ $x$

= $x^{2}$ $+$ $x$

Going on,

$g_{2}(x)$

= $g_{1}(x^{2}$ $+$ $2x)$ $-$ $g_{1}(x)$

= $(x^{2}$ $+$ $2x)^{2}$ $-$ $x^{2}$ $-$ $x$ by substituting $g_{1}(x)$ back into the expression previously obtained.

= ... $+$ $4x^{2}$ $+$ $x$ , where degrees of $x$ greater than 2 can be ignored as it does not affect the coefficient of $x^{2}$

Repeat the process for further values of $k$ to obtain the coefficient of $x$ and $x^{2}$

$g_{3}(x)$ = ... $+$ $13x^{2}$ $+$ $x$

$g_{4}(x)$ = ... $+$ $40x^{2}$ $+$ $x$

Hence, observe the pattern for $g_{k}(x)$ for coefficient of $x^{2}$ that is as follows

$g_{1}(x)$ -> $\frac{3^{1}-1}{2}$ $x^{2}$ = $x^{2}$

$g_{2}(x)$ -> $\frac{3^{2}-1}{2}$ $x^{2}$ = $4x^{2}$

$g_{3}(x)$ -> $\frac{3^{3}-1}{2}$ $x^{2}$ = $13x^{2}$

$g_{4}(x)$ -> $\frac{3^{4}-1}{2}$ $x^{2}$ = $40x^{2}$

$g_{k}(x)$ -> $\frac{3^{k}-1}{2}$ $x^{2}$

Hence, we need to determine the last 3 digit for $3^{299}$ to determine the coefficient of $x^{2}$ of $g_{299}(x)$

The method I use is to use binomial theorem as follows :

$3^{299}$

= $3.3^{298}$

= $3.9^{149}$

= $3(10-1)^{149}$

= $3($ $(-1)^{149}$ + $\bigl(\begin{matrix}149\\ 1\end{matrix} \bigr)(-1)^{148}(10)^{1}$ + $\bigl(\begin{matrix}149\\ 2\end{matrix} \bigr)(-1)^{147}(10)^{2} )$

= $3($ $-1+1490-1102600)$

= $-333$

which also means that the last 3 digit is

= $1000 - 333$

= $667$

Hence, reapply the last 3 digits of $3^{299}$ to the general formula, we get,

$g_{k}(x)$ -> $\frac{3^{k}-1}{2}$ $x^{2}$

$g_{299}(x)$ -> $\frac{3^{299}-1}{2}$ $x^{2}$

= $\frac{666}{2}$ $x^{2}$

= $333$ $x^{2}$

Thus, the coefficient of $x^{2}$ in $g_{299}(x)$ is 333.

To get a feel of the recurrence we calculate the first few terms -

$g_1(x) = g_0(x^2 + 2x) - g_0(x) = x^2 + 2x - x = x^2 + x\\ g_2(x) = ((x^2+2x)^2 + x^2 + 2x) - (x^2+x)\\ \qquad \, \, = x^4 + 4x^3 + 4x^2 + x^2 + 2x - x^2 - x\\ \qquad \, \, = x^4 + 4x^3 + 4x^2 + x$

Now we notice that $x^3$ terms or higher are irrelevant to the $x^2$ coefficient - they are never reduced down to $x^2$ or lower terms again, so can have no effect on the coefficient of $x^2$ . This means we can just look at the recurrence in terms of the $x^2$ and $x$ terms, casting out any higher terms.

Finding the recurrence and general formula for the $x^2$ term -

Starting from $g_k(x) = ax^2 + bx + \mathcal{O}(x^3)$ ,

$g_{k+1}(x) = a(x^2 + 2x)^2 + b(x^2 + 2x) - (ax^2 + bx) + \mathcal{O}(x^3)\\ \qquad \quad \, \, = ax^4 + 4ax^3 + 4ax^2 + bx^2 + 2bx - ax^2 - bx + \mathcal{O}(x^3)\\ \qquad \quad \, \, = (3a+b)x^2 + bx + \mathcal{O}(x^3)$

Using $a_k$ to refer to the coefficient of $x^2$ in $g_k(x)$ , we can write that $a_{k+1} = 3a_k + b$ , where $b$ is the coefficient of $x$ in $g_0(x)$ (or any other $g_k(x)$ , as the recurrence found above tells us it does not change). In this particular case, $a_{k+1} = 3a_k + 1$ .

To turn this into a homogeneous recurrence equation, we note that $a_{k+2} - 3a_{k+1} = 1 = a_{k+1} - 3a_k$ , so that $\\ \qquad a_{k+2} = 4a_{k+1} - 3a_k$ .

We now solve this in the usual manner - the characteristic quadratic here is $x^2 = 4x - 3, x^2 - 4x + 3 = 0, (x-3)(x-1) = 0$ , so $a_k$ can be expressed in the form $A(3)^k + B(1)^k = A(3)^k + B$ . Looking at the first two polynomials gives the simultaneous equations

$\qquad A(3)^0 + B = A+B = 0 \\ \qquad A(3)^1 + B = 3A + B = 1 \\ \qquad 2A = 1, A = \frac{1}{2}, B = -\frac{1}{2}$

which means that

$\qquad a_k = \frac{3^k - 1}{2}$ .

Finding the last $3$ digits of the $x^2$ coefficient for $g_{299}(x)$ -

In particular, the $x^2$ coefficient in $g_{299}(x)$ is $\frac{3^{299} - 1}{2}$ . This is impractical to calculate, but this can be mostly avoided in the following manner -

$\qquad \frac{3^{299} - 1}{2} = \frac{3^{300} - 1}{2} + \frac{3^{299} - 3^{300}}{2} \\ \qquad \qquad \: \; = \frac{3^{300} - 1}{2} + \frac{3^{299}(1-3)}{2} \\ \qquad \qquad \: \; = \frac{3^{300} - 1}{2} - 3^{299}$

If we now find $\frac{3^{300}-1}{2} \pmod{1000}$ , this should make it easier to find $\frac{3^{299}-1}{2} \pmod{1000}$ .

Using the generalisation to Fermat's little theorem, that $x^{\phi(n)} \equiv 1 \pmod{n}$ , we have that $3^{100} \equiv 1 \pmod{125}$ , because $\phi(125) = 125(\frac{4}{5}) = 100$ . This means $3^{300} \equiv 1 \pmod{125}$ .

Then, by simple calculation, we find $3^4 \equiv 9^2 \equiv 1 \pmod{16}$ , so $3^{300} \equiv 1 \pmod{16}$ .

Together these imply $3^{300} \equiv 1 \pmod{2000}$ . This means $3^{300} - 1 \equiv 0 \pmod{2000}$ and $\frac{3^{300}-1}{2} \equiv 0 \pmod{1000}$ .

Putting this into the earlier equations, we have that

$\qquad \quad \frac{3^{299}-1}{2} \equiv -3^{299} \pmod{1000}$

But $3^{300} \equiv 1 \pmod{1000}$ . If we let $x=3^{299}$ , then $3x \equiv 1 \pmod{1000}$ . A little consideration throws up $x=667$ as a solution, which is unique because of the uniqueness of multiplicative inverses. Therefore, $3^{299} \equiv 667 \pmod{1000}$ .

Putting this back in,

$\qquad \quad \frac{3^{299}-1}{2} \equiv -3^{299} \equiv 1000-667 \equiv 333 \pmod{1000}$

Which means that the last $3$ digits of the $x^2$ coefficient in $g_{299}(x)$ are $\underline{333}$ .

By induction we can easily prove that the coefficient of x^2 in g_{n}(x) is \frac {3^n - 1}{2}

It's easy to check that: 3^20 \equiv 4401 \pmod{10000} Then 3^40 \equiv 8801 \pmod{10000}, 3^60 \equiv 3201 \pmod{10000}, 3^80 \equiv 7601 \pmod{10000}, 3^100 \equiv 2001 \pmod{10000},

Hence 3^300 \equiv 2001 \pmod{10000} Denote 3^300=10000 \times k + 2001 Then k \equiv 0 \pmod{3} Thus 3^299 \equiv 0667 \pmod{10000} Therefore \frac {3^299-1}{2} \equiv 333 \pmod{1000} The answer is 333.

Let the coefficient of $x^2$ and $x$ in $g_k(x)$ be defined by the functions $m(k)$ and $n(k)$ respectively for all positive integers $k>0$ . Now we should find the coefficient of $x^2$ and $x$ in $g_k(x^2 + 2x)$ . Note that the term $x^2$ will occur in the expansion of $g_k(x^2 + 2x)$ only in the terms $(x^2 + 2x)^2$ and $x^2 + 2x$ , because in all other terms in the expansion of $g_k(x^2 + 2x)$ , the power of $x$ will be greater than $2$ . Similarly the term $x$ will occur in the expansion of $g_k(x^2 + 2x)$ only in the term $x^2 + 2x$ . Now coefficient of $x^2 + 2x$ in $g_k(x^2 + 2x)$ is $n(k)$ , and coefficient of $(x^2 + 2x)^2$ in $g_k(x^2 + 2x)$ is $m(k)$ . Since coefficient of $x$ in $x^2 + 2x$ is $2$ , coefficient of $x$ in $g_k(x^2 + 2x)$ will be $2n(k)$ . Again since coefficient of $x^2$ in $x^2 + 2x$ is $1$ and that in $(x^2 + 2x)^2$ is $4$ , coefficient of $x^2$ in $g_k(x^2 + 2x)$ will be $4m(k) + n(k)$ . Now coefficient of $x^2$ in $g_k(x)$ is $m(k)$ , and that of $x$ in $g_k(x)$ is $n(k)$ . Thus coefficient of $x^2$ in $g_{k+1}(x)$ = $4m(k) + n(k) - m(k)= 3m(k) + n(k)$ , and coefficient of $x$ in $g_{k+1}(x)$ = $2n(k)-n(k) = n(k)$ . Thus we obtain $m(k+1)= 3m(k) + n(k)$ , $n(k+1)= n(k)$ . Hence we can conclude that $n(k)$ is constant. Since $n(0)= 1$ , $n(k)= 1$ for all $k$ . Thus $m(k+1)= 3m(k)+1$ . To apply characteristic equation, we should establish a relation between $m(k+2)$ , $m(k+1)$ , and $m(k)$ . Note that $m(k+2)= 3m(k+1) + 1= 3m(k+1) + m(k+1) - 3m(k)= 4m(k+1) - 3m(k)$ . This implies $m(k+2) - 4m(k+1) + 3m(k)= 0$ . Hence the characteristic equation of this recurrence relation will be $x^2 - 4x + 3= 0$ . Note that $x^2 - 4x + 3= (x-1)(x-3)$ . Thus the roots of the characteristic equation will be $1$ and $3$ . Thus we can conclude that for all $k$ , $m(k)= p*1^k + q*3^k= p + q*3^k$ , where $p$ and $q$ are constants. Now the values of $p$ and $q$ have to be found. Note that $m(0)= 0$ , so $p+q= 0 .....(1)$ , and note that $m(1)= 3m(0)+1= 1$ , so $p+3q= 1 .....(2)$ . Subtracting equation $1$ from equation $2$ , we obtain $2q= 1 \implies q= \frac{1}{2}$ . Plugging this value of $q$ into equation $1$ , we obtain $p= -\frac{1}{2}$ . Thus for all $k$ , $m(k)= -\frac{1}{2} + \frac{1}{2}*3^k = \frac{3^k - 1}{2}= 3^{k-1} + 3^{k-2} + ... + 1$ . According to the question $k= 299$ , so we should find the value of $\frac{3^{299} - 1}{2}$ modulo $1000$ , which is $333$ . So our final answer is $333$ .

We prove, by induction on $k$ , that $g_k(x) = x + c_kx^2 + x^3 \cdot h_k$ , where $h_k$ is some polynomial in $x$ , so that we need to find $c_{299} \bmod 1000$ . Moreover, we also show that $c_k = \frac{3^k - 1}{2}$ .

Base Case: $k = 0$ : $g_k(x) = x = x + 0 \cdot x^2 + x^3 \cdot (0)$ , as needed. Moreover, we also have that $0 = \frac{1 - 1}{2} = \frac{3^0 - 1}{2}$ .

Induction Step: Assume that $g_k(x) = x + c_kx^2 + x^3 \cdot h_k$ , and $c_k = \frac{3^k - 1}{2}$ . Then, by definition,

$g_{k + 1}(x) = g_k(x^2 + 2x) - g_k(x)$ $= (x^2 + 2x) + c_k(x^2 + 2x)^2 + (x^2 + 2x)^3 \cdot h_k - \left( x + c_kx^2 + x^3 \cdot h_k \right)$ $= x + (3c_k + 1)x^2 + 4c_kx^3 + c_kx^4 + (x^6 + 6x^5 + 12x^4 + 7x^3) \cdot h_k$ $= x + (3c_k + 1)x^2 + x^3 \cdot \left( 4c_k + c_kx + (x^3 + 6x^2 + 12x + 7) \cdot h_k \right)$ ,

and so $g_{k + 1}(x)$ is of the necessary form, and moreover, $c_{k + 1} = 3c_k + 1 = 3 \cdot \frac{3^k - 1}{2} + 1 = \frac{3^{k + 1} - 3}{2} + \frac{2}{2} = \frac{3^{k + 1} - 1}{2}$ .

It remains to calculate $c_{299} = \frac{3^{299} - 1}{2} \bmod 1000$ . Now, $3^{299} = 3 \cdot 9^{149} = 3 \cdot (10 - 1)^{149}$ . By the binomial theorem, this expands to $3 \cdot \sum_{k = 0}^{149}{{149 \choose k}10^k(-1)^{149 - k}}$ which is equivalent to $3 \cdot ({149 \choose 0}10^0(-1)^{149} + {149 \choose 1}10^1(-1)^{148} + {149 \choose 2}10^2(-1)^147) \bmod 1000$ , since every other term of the sum is divisible by 1000. Furthermore, we see by straightforward calculation that this value is equivalent to $3 \cdot (-1 + 149 \cdot 10 + 11026 \cdot 100 \cdot -1) = -3303333 \equiv 667 \bmod 1000$ . Therefore, $\frac{3^{299} - 1}{2} \equiv \frac{667 - 1}{2} \equiv 333 \bmod 1000$ , and so $c_{299} = 333$ .

Note: This is only one of many ways of calculating $3^{299} \bmod 1000$ . Another method is to recall that $\lambda(1000) = 100$ where $\lambda(n)$ is the $n$ th Carmichael number, and so $3^{100} \equiv 1 \bmod 1000$ . Using the extended Euclidean algorithm, it follows that $3^{99} \equiv 667 \bmod 100$ and so $3^{299} \equiv 667 \bmod 1000$ .

Consider a fixed $k$ . Let $g_k(x) = \sum_{i=0}^n a_nx^n$ . From the formula to compute $g_{k+1}$ we can easily see that the coefficient of $x^2$ in $g_{k+1}$ only depends on $(a_0,a_1,a_2)$ , because higher powers of $x^2+2x$ do not contain the term $x^2$ . Hence it is sufficient to keep track of the last three coefficients of each polynomial.

Additionally, we can easily see that in each $g_k$ the units coefficient is $a_0=0$ (obvious) and the coefficient of $x^1$ is $a_1=1$ (easily proved by induction).

This leaves us with a single remaining step: given the coefficient $a_2$ of $x^2$ in $g_k$ , we should compute the coefficient of $x^2$ in $g_{k+1}$ . From the definition of $g_{k+1}$ we easily obtain that the new coefficient is $4a_2 + a_1 - a_2 = 3a_2 + a_1 = 3a_2+1$ .

Together with the initial condition that in $g_0$ the coefficient of $x^2$ is $0$ , this produces the sequence 0, 1, 4, 13, 40, 121, 364, ... Note that the initial terms of this sequence can also be obtained by completely evaluating the first few terms of our polynomial sequence. And having these terms, guessing the pattern is trivial.

We can now use the obtained recurrence to compute the required coefficient in $g_{299}$ directly (possibly doing all operations modulo 1000 to avoid large numbers). Alternately, we may note that our coefficient in $g_i$ can be written as $(3^i-1)/2$ .

$g_{0}(x)=x$ , and coefficient of $x^2$ is 0, $g_{1}(x)=x^2+x$ , and coefficient of $x^2$ is 1, $g_{2}(x)=x^4+4x^3+4x^2+x$ , and coefficient of $x^2$ is 4, then for $g_{3}$ , we only need to focus the quadratic terms, which is $4(x^2+2x)^2-4x^2$ , (the first term is from $g_{3}$ and the second term is from $g_{2}$ .) And coefficient of $x^2$ in $g_{3}$ is 40. Now we can let the coefficient of $g_{0}(x)$ be $a_{0}$ and so on. Then $a_{0}=0, a_{1}=1,a_{2}=4,a_{3}=13, a_{4}=40....,a_{n}=3a_{n-1}+1$ , and therefore $a_{n}=3(3a_{n-2}+1)+1=3^2a_{n-2}+3+1=3^2(3a_{n-1})+3+1= ... =3^{n-1}+3^{n-2}+3^{n-3}+...+3^2+3+1=(3^n-1)/2$ So now we need to figure out the last three digits of $(3^{299}-1)/2$ . And we know the last 3 digits of power of 3 repeats every 100 terms , i.e. the last 3 digits of $3^0$ is $001$ and it is the same as $3^{100}$ . Therefore the last three digits of $3^{299}$ must be $667$ in order to let the last three digits of $3^{300}$ be $001$ again. Then the last three digits $(3^{299}-1)/2$ is $(667-1)/2=333$ .

Define polynomial $f_k(x)$ as $g_k(x-1)$ . Then $f_0(x)=x-1$ and the recursive equation rewrites as follows: $f_{k+1}(x)=g_{k+1}(x-1)=g_k((x-1)^2+2(x-1))-g_k(x-1)=$ $=g_k(x^2-1)-g_k(x-1)=f_k(x^2)-f_k(x)$

The first few polynomials $f_i(x)$ are:

$\begin{aligned} f_1(x) &=x^2-x \\ f_2(x) &=x^4-2x^2+x\\ f_3(x) &=x^8-3x^4+3x^2-x\\ \end{aligned}$

Notice how the binomial coefficients appear. One can prove by induction that for all $k\geq 1$ $f_k(x)=\sum \limits_{i=0}^k \frac{k!}{i!(k-i)!} (-1)^{k-i} x^{2^i}$ Therefore, $g_k(x)=\sum \limits_{i=0}^k \frac{k!}{i!(k-i)!} (-1)^{k-i} (x+1)^{2^i}$ The coefficient of $x^2$ in $g_k(x)$ is $\sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} \frac{2^i(2^i-1)}{2}$ . This equals $\frac{1}{2}\left( \sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} 2^{2i} - \sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} 2^{i}\right) = \frac{(-1+4)^k-(-1+2)^k}{2} =\frac{3^k-1}{2}$

To find the last three digits of $\frac{3^{299}-1}{2}$ , we first note that $3^4=81\equiv 1 \pmod {16},$ so $3^{299} \equiv 3^3 \equiv 11 \pmod {16}$ . Therefore $\frac{3^{299}-1}{2}\equiv 5\pmod 8$ . Also, by Euler's theorem, $3^{100}\equiv 1 \pmod {125}$ . So $3^{299}\equiv \frac{1}{3} \equiv 42\pmod {125}$ . So $\frac{3^{299}-1}{2}\equiv 83 \pmod {125}.$ Putting these together and considering that $125\equiv 1 \pmod 8$ , the last three digits of $\frac{3^{299}-1}{2}$ are $83+2\cdot 125= 333.$