Question

[Weekend Challenge - Solved by @adxpoi and @oldrin.bataku ] Suppose \(P(x)\) is a polynomial of degree \(10\) such that \(P(k) = 2^k\) for all \(k=0,1,2,\ldots,10\).

Find the value of \(P(11)\)

Answer 1

\[P(x)=a_{10}x^{10}+a_9x^9+a_8x^8+a_7x^7+a_6x^6+a_5x^5+a_4x^4+a_3x^3 + \\ +a_2x^2+a_1x^+a_0 \\ P(0)=1 \\ a_0=1 \\ \]
well I know there is a really long way...
pluggin in all those critters to find the constant coefficients of the polynomial P

Answer 2

4095?

Answer 3

11 equations and 11 unknowns is solvable for sure :)

Answer 4

@ospreytriple nope, but it seems you got it!
the answer is \(2047\)

Answer 5

please post your method, im pretty sure it is just a typo somewhere..

Answer 6

Darn. Added an extra factor of 2 somewhere. :)

Answer 7

Not sure if I understood the question but the condition that \(P(k)=2^k\) got me thinking that the answer was simply \(P(11)=2^{11}+2^{10}+...+2^1+2^0

Answer 8

why not 2048?

Answer 9

never mind

Answer 10

Because we only know \(11\) values of function \(P(x)\), namely, \(P(0), P(1), P(2),\ldots,P(10)\)

we don't know the value of\(P(x)\) for other values of \(x\)

Answer 11

Consider the polynomial \[Q(x) = \sum_{j=0}^{10} (-1)^{10-j}\frac{2^j}{j!(10-j)!}l_j(x)\]
where \(l_j(x) = \frac{x(x-1)...(x-10)}{(x-j)}\)
[\(Q(x)\) is basically the Lagrange Interpolation polynomial with data points \((0,1),(1,2),(2,2^2),...,(10,2^{10})\)]

Note that \(l_j(j) = (-1)^{10-j}j!(10-j)!\)
Therefore, \(Q(j) = 2^j\) for \(j = 0\) to \(10\)
\(Q(x)\) is a polynomial of degree at most \(10\) so, \(Q(x)-P(x)\) is also a polynomail of degree at most \(10\)
Also, \(Q(x)-P(x) = 0\) for \(11\) values of \(x\). Therefore, \(Q(x) -P(x)\) ia identically zero.
That is, \(Q(x) = P(x)\)
Therefore, \(P(11)\)
\( = Q(11)\)
\( = \sum_{j=0}^{10} (-1)^{10-j}\frac{2^j}{j!(10-j)!}l_j(11)\)
\( = \sum_{j=0}^{10} (-1)^{10-j}\frac{2^j}{j!(10-j)!}\frac{11!}{(11-j)}\)
\( = \sum_{j=0}^{10} (-1)^j2^j\left(\begin{matrix}11 \\ j\end{matrix}\right)\)
\( = 2^{11} - (2-1)^{11}\)
\( = 2^{11} - 1\)

Answer 12

@adxpoi did it correctly, although I used Newton polynomials

Answer 13

consider the finite differences:

1
1
2 1
2
4 2
4
8 4
8
16 8
16
32

which is a consequence of the fact that \(2^k=2\cdot2^{k-1}=2^{k-1}+2^{k-1}\).
now consider
$$
P(n)=\sum_{k=0}^{10}\binom{n}{k}\Delta^k[P](0)\\P(11)=\sum_{k=0}^{10}\binom{11}k\cdot 1=\sum_{k=0}^{10}\binom{11}k
$$

now using the binomial theorem, we have that: $$2^{11}=\left(1+1\right)^{11}=\sum_{k=0}^{11}\binom{11}k\\2^{11}-1=\sum_{k=0}^{10}\binom{11}k$$

giving us \(P(11)=2^{11}-1=2047\)

Answer 14

alternatively, if you understand that \(2^n\) has identical finite differences, i.e. \(\Delta^k[2^n]=2^n\), then we should expect that for our \(10\)th degree polynomial once we reach our \(10\)th difference we'll hit all constants, which must be \(1,1,\dots\). however, for \(2^n\) it would have been changing again, so \(1,2,\dots\).

Answer 15

so for the \(11\)th term, in which we'll make use of our eleventh difference at \(0\), we expect \(\Delta^{11}[P]=0\), while for \(2^n\) we'd have \(\Delta^{11}[2^n]=1\). hence our result will be \(1\) less than\(2^11\)

Answer 16

Excellent! both methods look great!
In summary, the polynomial that satisfies given data points is
\[\large P(x) = \sum\limits_{i=0}^{10} \binom{x}{i}\]
plugging in \(x=11\) gives \(P(11) = 2^{11}-1\)

Answer 17

I tried the brute force method. With\[P(x) = a_{10}x^{10} + a_9x^9+a_8x^8+a_7x^7+a_6x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+a_0\]and knowing that\[P(0)=1\]\[P(1)=2\]\[P(2)=4\]\[P(3)=8\]\[P(4)=16\]\[P(5)=32\]\[P(6)=64\]\[P(7)=128\]\[P(8)=256\]\[P(9)=512\]\[P(10)=1024\]I created an augmented matrix and after a lot of Gauss-Jordan elimination determined that\[a_{10}=2.75576\times10^{-7}\]\[a_9=-9.64519\times10^{-6}\]\[a_8=1.65347\times10^{-4}\]\[a_7=-1.59560\times10^{-3}\]\[a_6=1.01449\times10^{-2}\]\[a_5=-3.87451\times10^{-2}\]\[a_4=1.12450\times10^{-1}\]\[a_3=-1.05290\times10^{-1}\]\[a_2=3.77246\times10^{-1}\]\[a_1=6.45634\times10^{-1}\]\[a_0=1\]I kept about double these number of decimal places and confirmed the results using Excel. After confirming the value of the coefficients, I was able to calculate\[P(11)=2047\]I'm tired now :)