Polynomial Recursion

From the definition, we have $f_{10}(x) = f_9(x+1)+x^{10}$

But $f_9(x+1) = f_8(x+2)+(x+1)^9$ so $f_{10}(x) = f_8(x+2)+(x+1)^9+x^{10}$ and $f_8(x+2)=f_7(x+3)+(x+2)^8$ so $f_{10}(x) = f_7(x+3)+(x+2)^8+(x+1)^9+x^{10}$ .

Continuing in this pattern, we reach $f_{10}(x) = f_0(x+10)+(x+9)^1+(x+8)^2+\ldots+(x+1)^9+x^{10}$

We are looking for the coefficient of x, which is the sum of the coefficients of x in the individual terms. Using the binomial theorem, we have the coefficient of x in $(x+9)^1$ as ${1 \choose 1}9^0$ , the coefficient of x in $(x+8)^2$ as ${2 \choose 1}8^1$ , that in $(x+7)^3$ as ${3 \choose 1}7^2$ and in general, the coefficient of x in $(x+a)^{10-a}$ as ${{10-a} \choose 1}a^{9-a}=(10-a)a^{9-a}$ .

Therefore, our expression for the coefficient of x in the sum is $1\times 9^0+2\times 8^1+3\times 7^2+\ldots+8\times2^7+9\times 1^8$

We must take the the last 3 digits in the sum, which can be done by taking the last 3 digits in the individual terms, so our sum becomes $1+16+147+864+125+144+103+24+9=1433$

The last 3 digits of that is $\boxed{433}$ , our answer.

I claim that for every positive integer $n$ ,

$\begin{aligned} f_n(x)&=&\sum_{i=0}^n(x+i)^{n-i}\\ \end{aligned}$

We will prove this by induction.

The base case $n=0$ trivially holds, so let us now assume that $f_n(x)=\sum_{i=0}^n(x+i)^{n-i}$ holds for some $n$ . Replacing $x$ with $x+1$ gives $f_n(x+1)=\sum_{i=0}^n(x+1+i)^{n-i}$ . Then $\begin{aligned} f_{n+1}(x)&=&f_{n}(x+1)+x^{n+1}\\ &=&x^{n+1}+\sum_{i=0}^n(x+1+i)^{n-i}\\ &=&\sum_{i=0}^{n+1}(x+i)^{n+1-i}, \end{aligned}$ and our induction is complete.

Thus for the case of $n=10$ , we have $f_{10}(x)=x^{10}+(x+1)^9+(x+2)^8+(x+3)^7+\cdots+(x+9)+1$ By the Binomial Theorem, the coefficient of $x$ is $1^8\cdot 9+2^7\cdot 8+3^6\cdot 7+\cdots+9^1\cdot 1+1=16433$ The requested answer is $\boxed{433}$ .

In order to find the coefficient of x we need to iterate the formula until we obtain a plain formula: $f_{10}(x) = f_{9}(x + 1) + x^{10} = f_{8}(x+2) + (x+1)^9 + x^{10}$ $= f_{7}(x+3) + (x+2)^8 + (x+1)^9 + x^{10}$ $= f_{6}(x+4) + (x+3)^7 + (x+2)^8 + (x+1)^9 + x^{10}$

$...$

$= f_{0}(x+10) + (x+9)^1 + (x+8)^2 + (x+7)^3 + (x+6)^4 + (x+5)^5 + (x+4)^6 + (x+3)^7 + (x+2)^8 + (x+1)^9 + x^{10}$ $= 1 + (x+9)^1 + (x+8)^2 + (x+7)^3 + (x+6)^4 + (x+5)^5 + (x+4)^6 + (x+3)^7 + (x+2)^8 + (x+1)^9 + x^{10}$

Now we perform the calculation of each term, just worrying about the x coefficient. For instance $(x + 9)^1$ has x coefficient 1. And $(x+8)^2 = x^2 + 2\times 8^1\times x +64$ has x coefficient $2\times 8^1\times x$

Continuing all the calculations, we get:

$1\times x + 2\times 8^1\times x + 3\times 7^2\times x + 4\times 6^3\times x + 5\times 5^4\times x + 6\times 4^5\times x + 7\times 3^6\times x + 8\times 2^7\times x + 9\times 1^8\times x$

This results in $16433 \times x$ . This is the x coefficient we are looking for and the last 3 digits are $433$ .

It can be easily observed by expansion that $f_n (x) = \displaystyle \sum_{k=0}^n (x+n-k)^k$

In specific, $f_{10} (x) = \displaystyle \sum_{k=0}^{10} (x+10-k)^k$

By binomial expansion, the coefficient of x is $\displaystyle \sum_{k=2}^9 k(10-k)^{k-1}$ , of which the last three digits are 433.

f 0(x) = 1 f 1(x) = 1 + x f 2(x) = 1 + (x+1) + x^2 f 3(x) = 1 + (x+2) + (x+1)^2 + x^3 f 4(x) = 1 + (x+3) + (x+2)^2 + (x+1)^3 + x^4 ... Continuing the pattern would show that: f 10(x) = 1 + (x+9) + (x+8)^2 + (x+7)^3 + ... + (x+2)^8 + (x+1)^9 + x^10 Using the Binomial Theorem, the coefficients of x for each expansion can be obtained. The coefficient of x in (x+9) is 1. The coefficient of x in (x+8)^2 is ( 2C 1)(8). The coefficient of x in (x+7)^3 is ( 3C 2)(7^2). The coefficient of x in (x+6)^4 is ( 4C 3)(6^3). The total sum can then be expressed as: \displaystyle \sum_{i=1}^9 (10-i)(i^(9-i)). Solving this expression gives the total of 16433. Therefore, the last 3 digits of the coefficient of x are 433.

We have $f_0(x)=1$ , $f_1(x)=x+1$ , $f_2(x)=x^2+(x+1)+1$ , $f_3(x)=x^3+(x+1)^2+(x+2)^1+1$ .... continuing so we have that $f_{10}(x)=x^{10}+(x+1)^9+(x+2)^8+(x+3)^7+ (x+4)^6 +... \\ ...+(x+8)^2+(x+9)^1+1$ .

Each term has the form $(x+k)^{10-k} , \ k=0,1,2,...,10$ . The coefficient of $x$ in each term is given by $(10-k)k^{10-k-1}$ due to the binomial teorem. The coefficient of $x$ in $f_{10}(x)$ is given by the sum of the coefficient of each term. So it is given by: $9\cdot 1^8+ 8\cdot 2^7+7\cdot 3^6 + 6\cdot 4^5+5\cdot 5^4+ 4\cdot 6^3+3\cdot 7^2+2\cdot 8^1+1$ . This is equal to $16433$ , so the last $3$ digits are $433$ .

note that:

f 0(x)=1 f 1(x)=1 + x f 2(x)=1 + (x+1) + (x)^2 f 3(x)=1 + (x+2) + (x+1)^2 + x^3 . . . . f_{10}(x)= 1 + (x+9) + (x+8)^2 + (x+7)^3 + (x+6)^4 + (x+5)^5 + (x+4)^6 +(x+3)^7 + (x+2)^8 + (x+1)^9 +x^{10}

and using the binomial theorem, we get the following coefficients of x of the the powers of (x+k), k=1,2,..10.

(x+9) =1 (x+8)^2=16 (x+7)^3=147 (x+6)^4=864 (x+5)^5=3125 (x+4)^6=6144 (x+3)^7=5103 (x+2)^8=1024 (x+1)^9=9 x^{10}=0

which is when you add, you will get 16433.

$f_{10}(x) = f_9(x+1) + x^{10}$ and $f_9(x+1) = f_8(x+2) + (x+1)^9$ and so on for $f_8(x+2)$ till $f_1(x+9)$ and $f_0(x+10) = 1$

therefore $f_{10}(x) = x^{10} + (x+1)^9 + (x+2)^8 + (x+3)^7 +(x+4)^6$ $+(x+5)^5+(x+6)^4+(x+7)^3+(x+8)^2+(x+9)^1$ and sum coefficient of x in all the above terms will be:- $9c1*1 + 8c1*2^7 + 7c1*3^6 + 6c1*4^5 + 5c1*5^5 + 4c1*6^3 + 3c1*7^2 + 2c1*8^1 + 1$ $= 9 + 1024 + 5103 + 6144 + 3125 + 864 + 147 + 16 +1$ $= 16433$ therefore the last 3 digits of the coefficient of $x$ in $f_{10}(x)$ is $433$ .

Just see the recursion... We get f10(x) = f9(x+1)+x^10=f8(x+2)+(x+1)^9+x^10=f7(x+3)+(x+2)^8+(x+1)^9+x^10=......(continue by yourself)=Ʃ(x+k)^(10-k) Using the binomial newton theorem, we can see Coefficient of x in (x+k)^(10-k) is (10-k) (k^(9-k)) So, we just find the value of \displaystyle \sum_{i=1}^3 (10-k) (k^(9-k)) And just a little work to count them we get 16433... And the last 3 digits of the coefficient of x is 433...

Keep rewriting f10, f9, f8, ..., until you reach f0. f10(x) = f9(x+1) + x^10 f9(x+1) = f8(x+2) + (x+1)^9 f8(x+2) = f7(x+3) + (x+2)^8 f7(x+3) = f6(x+4) + (x+3)^7 ... f3(x+7) = f2(x+8) + (x+7)^3 f2(x+8) = f1(x+9) + (x+8)^2 f1(x+9) = f0(x+10) + (x+9)^1 f0(x+10) = f0(x) = 1

Now, work your way back up and you'll get. f10(x) = x^10 + (x+1)^9 + (x+2)^8 + (x+3)^7 + ... + (x+8)^2 + (x+9)^1 +1 X coeff= 0 + 9 1^8 + 8 2^7 + 7 3^6 + 6 4^5 + ... + 2 8^1 + 1 9^0 X coeff= 16433

If you were confused by the above step, here is an example with calculating the coefficient of x in the (x+3)^7 term. (x+3)^7 = (x+3)(x+3)(x+3)(x+3)(x+3)(x+3)(x+3) In 6 of those terms, we need to multiply by a 3. In 1 of those terms, we need to multiply by a 1x. There are 7C1 ways to pick which factor gives the x. 7C1 * 3^6 * 1 = 5103

Define $g_k(x)$ to be the derivative of $f_k(x)$ . Then $g_0(x)=0$ and, differentiating the functional equation for $f_{k+1},$ $g_{k+1}(x)=g_k(x+1)+(k+1)x^k$

Note that the coefficient we are looking for is $g_{10}(0)$ . Applying the recursive formula for $g_{10},\ g_9$ and so on, we get: $g_{10}(0)=g_9(1)+10\cdot 0^9=g_8(2)+9\cdot 1^8+10\cdot 0^9=g_7(3)+ 8\cdot 2^7+ 9\cdot 1^8+10\cdot 0^9=$ $=...=g_0(10)+\left(1\cdot 9^0+2\cdot 8^1 +...+ 9\cdot 1^8+10\cdot 0^9\right)$ Because $g_0(10)=0,$ we just need to calculate the last three digits of the sum $1\cdot 9^0+2\cdot 8^1 +...+ 9\cdot 1^8+10\cdot 0^9$ . This sum is $1+16+3\cdot 49+4\cdot 6^3+5\cdot 5^4+ 6\cdot 4^5+7\cdot 3^6+ 8\cdot 2^7+9+0=$ $=1+16+147+864+3125+6144+5103+1024+9=16433$ So the answer is $433$ .

First observe that the coefficient of $x$ in $f_{10}(x)$ is equal to $f_{9}'(1)$ . In fact if $P(x)=a_nx^n+\cdots a_1x+a_0$ then $P(x+1)=a_n(x+1)^n+\cdots +a_1(x+1)+a_0=$ $a_nx^n+\cdots +({n\choose n-1}a_n+{n-1\choose n-2}a_{n-1}+\cdots +a_1)x+(a_0+a_1+\cdots +a_n)=$ $a_nx^n+\cdots +(na_n+(n-1)a_{n-1}+\cdots +a_1)x+(a_0+a_1+\cdots +a_n)=$ and $P'(x)=a_nnx^n+a_{n-1}(n-1)x^{n-1}+\cdots +a_1\implies$ $P'(1)=na_n+(n-1)a_{n-1}+\cdots +a_1$ . Now with this observation we just need to apply the derivative in the recurrence relation, use it with $f_{9}'(1)$ and complete taking $\pmod{1000}$ $f_{k+1}(x)=f_{k}(x+1)+x^{k+1}$ $f_{k+1}'(x)=f_{k}'(x+1)+(k+1)x^{k}\implies$ $f_{9}'(1)=f_{8}'(2)+9\cdot 1^{8}=$ $f_{7}'(3)+9\cdot 1^8+8\cdot 2^7=\cdots$ $=\displaystyle\sum_{k=1}^{9}k^{9-k}(10-k)\equiv$ $433\pmod{1000}$