A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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

  • This Question is Closed
  1. freckles
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    4095?

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    11 equations and 11 unknowns is solvable for sure :)

  4. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    why not 2048?

  9. triciaal
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    never mind

  10. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @adxpoi did it correctly, although I used Newton polynomials

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.