Polynomial powered by 2

We can construct a finite difference table: $\begin{array}{ccccccccccccccccc} f(0)&&f(1)&&f(2)&&f(3)&&f(4)&&f(5)&&f(6)&&f(7)&&f(8)\\\hline 1&&2&&4&&8&&16&&32&&64&&128&&256\\ &1&&2&&4&&8&&16&&32&&64&&128\\ &&1&&2&&4&&8&&16&&32&&64\\ &&&1&&2&&4&&8&&16&&32\\ &&&&1&&2&&4&&8&&16\\ &&&&&1&&2&&4&&8\\ &&&&&&1&&2&&4\\ &&&&&&&1&&2\\ &&&&&&&&1 \end{array}$ This last row has to be constant, so we can extend the finite difference table: $\begin{array}{ccccccccccccccccccc} f(0)&&f(1)&&f(2)&&f(3)&&f(4)&&f(5)&&f(6)&&f(7)&&f(8)&&f(9)\\\hline 1&&2&&4&&8&&16&&32&&64&&128&&256&&511\\ &1&&2&&4&&8&&16&&32&&64&&128&&255\\ &&1&&2&&4&&8&&16&&32&&64&&127\\ &&&1&&2&&4&&8&&16&&32&&63\\ &&&&1&&2&&4&&8&&16&&31\\ &&&&&1&&2&&4&&8&&15\\ &&&&&&1&&2&&4&&7\\ &&&&&&&1&&2&&3\\ &&&&&&&&1&&1 \end{array}$ Therefore, $f(9)=\boxed{511}$ .

Solution 1: Since we have 9 values for a degree 8 polynomial, this polynomial is uniquely determined.

For $i$ a non-negative integer, consider the polynomial ${ x \choose i} = \frac { (x) (x-1) \cdots (x-i+1) } { i!}$ . It is clear that $f(n) = \sum_{i=0}^8 { n \choose i}$ for $n = 0$ to 8. Hence, this must be the unique polynomial.

Thus, $f(9) = \sum_{i=0}^8 { 9 \choose i} = (1+1)^9 - { 9 \choose 9} = 511$ .

Solution 2: By the Lagrange Interpolation Formula, $f(9)=\sum \limits_{i=0}^{8}\frac{2^i\cdot \left(\prod \limits_{j=0}^{i-1} (9-j)\right)\cdot \left(\prod \limits_{j=i+1}^{8} (9-j)\right) }{\left(\prod \limits_{j=0}^{i-1} (i-j) \right)\cdot\left( \prod \limits_{j=i+1}^{8} (i-j)\right) }$ This equals $\sum \limits_{i=0}^{8} \frac{2^i\cdot 9!/(9-i)}{i!\cdot (-1)^{8-i}(8-i)!}=\sum \limits_{i=0}^{8}2^i\cdot (-1)^{8-i}\frac{9!}{i!(9-i)!}=-\sum \limits_{i=0}^{8} 2^i(-1)^{9-i}\frac{9!}{i!(9-i)!}$ By the Binomial Theorem applied to $(2-1)^9,$ this equals $-\left((2-1)^9-2^9\right)=2^9-1=511$

Solution 3: Since we know that $f(x)$ is a polynomial, we use the method of finite differences. We construct the table of differences as follows:

$\begin{array}{llllllllllllllllllll} 1 & & 2 & & 4 & & 8 & & 16 & & 32 & & 64 & & 128 & & 256 & & f(9) \\ & 1 & & 2 & & 4 & & 8 & & 16 & & 32 & & 64 & & 128 & & a & \\ & & 1 & & 2 & & 4 & & 8 & & 16 & & 32 & & 64 & & b & \\ & & & 1 & & 2 & & 4 & & 8 & & 16 & & 32 & & c \\ & & & & 1 & & 2 & & 4 & & 8 & & 16 & & d & \\ & & & & & 1 & & 2 & & 4 & & 8 & & e\\ & & & & & & 1 & & 2 & & 4 & & f\\ & & & & & & & 1 & & 2 & & g\\ & & & & & & & & 1 & & h\\ \end{array}$

This allows us to calculate that $h=1, g=3, f=7, e=15, d=31$ , $c=63, b=127, a= 255, f(9) = 511$ .

We have to find an 8 degree polynomial, namely $f(x)$ , so that we can find the value of $f(9)$ , since $i \neq 9$ . Let us consider 9 polynomial functions $P_0(x)$ , $P_1x)$ , $P_2(x)$ $...$ $P_8(x)$ .

Now

Let $P(x) =(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)$ Then $P(0)=(-1)(-2)(-3)(-4)(-5)(-6)(-7)(-8)$ $\Rightarrow P(0)=8!$ so, $P_0(x)= \frac {1}{8!} (x-1)(x-2)(x-3)(x-4)\ldots(x-8)$

let $P(x)=x(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)$ Then, $P(1)=(1)(-1)(-2)(-3)(-4)(-5)(-6)(-7)$ $\Rightarrow P(1)=-(7!)$ so, $P_1(x)=\frac{-1}{7!} x(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)$

Let $P(x)=x(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)$ Then, $P(2)=(2)(1)(-1)(-2)(-3)(-4)(-5)(-6)$ $\Rightarrow P(2)=(6!)(2)$ so, $P_2(x)=\frac {1}{(6!)(2)} x(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)$ Similarly, we can get the following: $P_3(x)=\frac {-1}{(3!)(5!)} x(x-1)(x-2)(x-4)(x-5)\ldots(x-8)$ $P_4(x)=\frac{1}{4! 4!} x(x-1)(x-2)(x-3)(x-5)(x-6)\ldots(x-8)$ $P_5(x)=\frac{-1}{5! 3!} x(x-1)(x-2)(x-3)(x-4)(x-6)\ldots(x-8)$ $P_6(x)=\frac{1}{6! 2!} x(x-1)(x-2)(x-3)(x-4)(x-5)(x-7)(x-8)$ $P_7(x)=\frac{-1}{7!} x(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-8)$ $P_8(x)=\frac{1}{8!} x(x-1)(x-2)(x-3)(x-4)\ldots(x-7)$

Now, $f(x)=P_0(x)+2P_1(x)+4P_2(x)+8P_3(x)+16P_4(x)+32P_5(x)+64P_6(x)+128P_7(x)+256P_8(x)$ Since: $f(i)=2^i$ for $i=0,1,2,3,4,5,6,7,8$ See The post on Lagrange Interpolation Formula.(To understand the above usage). Substituting for $x=9$ in the above equation we get the following: $f(9)=1-18+144-672+2016-4032+5376-4608+2304$ $\Rightarrow f(9)=511$

We see that the sequence of values of $f(i)$ for $i=0,1,\ldots,9$ are: $(1,2,4,8,16,32,64,128,256)$ . Next we see the difference between adjacent values to produce first order difference: $(1,2,4,8,16,32,64,128)$ , we repeat until we reach a constant value: $(1)$ , which is the eighth order difference. Since $f(i)$ is of order $8$ , there must be only one polynomial that satisfies that eighth order difference of $(1)$ , and it must be constant. So the second term of the eighth order difference should also be $1$ . Therefore we have the seventh order of difference: $(1,2,3)$ , the sixth $(1,2,4,7)$ , the fifth $(1,2,4,8,15)$ , and so on until the values $(1,2,4,8,16,32,64,128,256,511)$ . So $f(9)=511$ .

We can solve this by using Lagrange Interpolation Formula. By using the formula, the answer = 511

F(x) is a polynomial of degree 8. We know nine values of f(x), so we can use Lagrange interpolation formula; So, f(9)=1 ( (9-1) (9-2) (9-4) (9-8)...(9-256)/(0-1) (0-2) (0-4) (0-8)...(0-256)) + 2 *(((9-0) (9-2) (9-4) (9-8)...(9-256)/(1-0) (1-2) (1-4) (1-8)...(1-256))+ ...+ 256 (((9-0) (9-1) (9-2) (9-4)...(9-128)/(8-0) (8-1) (8-2) (8-3)...(8-7))=511

Since f(x) has degree 8, we assume it is of the following form:

$a_1 + a_2x + a_3x^2 + a_4x^3 + a_5x^4 + a_6x^5 + a_7x^6 + a_8x^7 + a_9x^8 = f(x)$

Since $f(i) = 2^i$ for i = 0, 1, 2, 3, 4, 5, 6, 7 and 8, we know that

$f(0) = 1, f(1) = 2, f(2) = 4, f(3) = 8, f(4) = 16,$ $f(5) = 32, f(6) = 64, f(7) = 128, f(8) = 256$

We can now make 9 equations by plugging in each x value and f(x) value into the original equation.

Solving the system of 9 equations will get you the following coefficients:

$a_1 = 1 a_2 = \frac{523}{840} a_3 = \frac{799}{2016}$ $a_4 = \frac{-31}{288} a_5 = \frac{63}{640} a_6 = \frac{-19}{720}$ $a_7 = \frac{1}{192} a_8 = \frac{-1}{2016} a_9 = \frac{1}{40320}$

Plugging in $x = 9$ to the 8th degree polynomial with those coefficients gives you 511.

We can use the method suggested here

https://brilliant.org/wiki/method-of-differences/

By creating a difference table and note that $D_{8}(n)$ is a constant which is $= 1$

The sequence $x_n=a_0+a_1n+\cdots+a_8n^8$ can be considered a linear combination of the sequences $1, n, n^2, \cdots, n^8.$ Using what is explained in the wiki Linear Recurrence- repeated roots, we obtain that the sequence $(x_n)_n$ satisfies a linear recurrence with characteristic polynomial $(r-1)^9.$ Therefore we have that for any natural number $n\geq 9,$ the following is always true $\sum_{k=0}^{9}{ {9}\choose {k}} (-1)^k x_{n-k} =0.$ Now, making $n=9$ and solving for $x_9,$ we get $x_9=-\sum _{k=1}^{9}{ {9}\choose {k}}(-1)^k x_{9-k}=-\sum _{k=1}^{9}{ {9}\choose {k}}(-1)^k 2^{9-k}=2^9-(2-1)^9=\boxed{511}.$

A polynomial of the 8th degree sounds scary, so we should start with simpler cases.

To begin with, look at the polynomial of 1st degree (a line) given that $f(i) = 2^{i}$ for i=0,1. This obviously generates a line with equation $y=x+1$ , and f(2) in this case (since we're looking for f(n+1) where n is the degree of the polynomial) = 3.

Next, we examine the case with a polynomial of degree 2, or a quadratic, given that $f(i) = 2^{i}$ for i=0,1,2. Solving the system of 3 equations with 3 variables, we find that $f(x) = 0.5x^{2}+0.5x+1$ , and f(3) = 7.

We're beginning to see a pattern here, of f(n+1), where the polynomial has degree of n, has a value of $2^{n+1}-1$ , but let's do another one to make sure. Again, we have a polynomial, this time of degree 3 and having $f(i) = 2^{i}$ for i=0,1,2,3. Solving the system of 4 variables and 4 equations, we get that $f(x) = x^{3}/6+5x/6+1$ , and f(4) = 15, which is equal to $2^{4}-1$ .

We now hypothesize that f(9) in the original problem follows our formula, thus $f(9) = 2^{9}-1 = 512-1 = 511$ , giving us the final answer of 511.

f(x)=1-7x+22x^2-40x^3+46x^4-34x^5+16x^6-4x^7+x^8) f(9)=511 because all but one (namely 1+1+1+...+1=10) of the 2^9 compositions of 10 are in nine or fewer parts. Sum C(n,k), k=0..8 series

1st, we will assume that the graph from points x={0,1,2,3,4,5,6,7,8} is exponential satisfying the equation f(x)=2^x.

So at point when x=8, the graph will have its turning point and change the direction of its graph satisfying the equation f(y)=2^y with origin at point (8,512). Now, by using f(y)=2^y, let y=0 resulting to x=1. Going back to the graph, we will have to subtract 512 by the value of x which is 1 resulting to the value now of f(9) equal to 511.

f(9)=Σ(2^i) (i=0 to 8)=2^9 -1=511

since it follows the general pattern given by them,f(0)=1. thus we found that the constant in the polynomial is 1. now f(9)=2^9-constant polynomial=512-1=511.