## ganeshie8 one year ago [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)$$

1. freckles

$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

2. anonymous

4095?

3. ganeshie8

11 equations and 11 unknowns is solvable for sure :)

4. ganeshie8

@ospreytriple nope, but it seems you got it! the answer is $$2047$$

5. ganeshie8

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

6. anonymous

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

7. anonymous

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 8. triciaal why not 2048? 9. triciaal never mind 10. ganeshie8 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$$

11. anonymous

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$$

12. anonymous

@adxpoi did it correctly, although I used Newton polynomials

13. anonymous

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$$

14. anonymous

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$$.

15. anonymous

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$$

16. ganeshie8

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$$

17. anonymous

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 :)

Find more explanations on OpenStudy