×

[Calvin] Which solution would you feature (8)?

Previous Discussion

Below, we present a problem from the 2/4 Algebra and Number Theory set, along with 3 student submitted solution. You may vote up for the solutions that you think should be featured, and should vote down for those solutions that you think are wrong (voting is anonymous!). Also, feel free to make remarks about these solutions, especially since threading of comments has been introduced :).

Polynomial powered by 2 A polynomial $$f(x)$$ has degree $$8$$ and $$f(i)=2^i$$ for $$i=0,1,2,3,4,5,6,7,8$$. Find $$f(9).$$

You may try the problem by clicking on the above link.

All solutions may have LaTeX edits to make the math appear properly. The exposition is presented as is, and has not been edited.

About 50% of those who answered this problem got it correct. Most guessed $$2^9 = 512$$, which is incorrect. The formula $$f(n) = 2^n$$ is an exponential, not a polynomial.

[I am aware of solutions using the Lagrange Interpolation Formula, though none of them bothered to write it up properly. Please do not post any other solutions.]

$\mbox{Remarks from Calvin}$

Solution A - This is a typical example of solutions obtained through lucky guessing. In this case, he happened to sum up the various values and got the answer of 511, so claimed that must be the solution. No justification for the steps have been given. While it can be considered the final step of Solution B, there is no indication that the method of differences is part of the thought process. Such a solution is marked incomplete at best.

Solution B - This is a great solution, for those who understand the method of differences for a polynomial. It is simple, direct, and works if you are given consecutive values of the polynomial. I like that he provided enough detail that I can tell he has the correct solution at one quick glance. This solution is presented by Ryan.

For those who do not know the method of differences, do a quick search on the internet or read the comments.

Solution C - Not every pattern can be proved by Mathematical Induction. In this case, because the polynomial is hard to generalize, the induction method will not work nicely. While that is not to say it is impossible, you will have to provide details of how to do the actual induction, and not merely "let's do another one to make sure".

Solution Karan - Calculus works on incremental changes, and not such discrete large step changes. As Peter points out, we know that exponential growth is much faster than polynomial growth, so there is no polynomial function with can take on values $$f(n) = 2^n$$ for all positive integers $$n$$. Try proving this fact, it can be slightly tricky!

Solution Titas - Clearly ignored my request to not state a solution using the Lagrange Interpolation Formula. Yes we know that it works, but the calculations can be tedious and are certainly non-enlightening. Here's a direct approach:

We know that binomial coefficients can be interpreted as polynomial. For example, $${ x \choose 3} = \frac {x (x-1)(x-2} { 3!}$$. I claim that the polynomial is equal to

${x \choose 0} + { x \choose 1} + { x \choose 2} + {x \choose 3} + {x \choose 4} + {x \choose 5} + { x \choose 6 } + { x \choose 7 } + { x \choose 8}.$

This follows since the above is a degree 8 polynomial that agrees on the 9 given values. Hence

$f(9) = {9 \choose 0} + { 9 \choose 1} + { 9 \choose 2} + {9 \choose 3} + {9 \choose 4} + {9 \choose 5} + { 9 \choose 6 } + { 9 \choose 7 } + { 9 \choose 8} = (1+1)^9 - 1 = 511.$

Note by Calvin Lin
4 years, 6 months ago

Sort by:

Solution B - 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}$$. Staff · 4 years, 6 months ago

This is clearly the clearest solution (no pun intended). It shows a nice visual representation of this problem and leaves out nothing for the reader to guess. · 4 years, 6 months ago

very good ...after knowing the solution,everything in the universe looks nice and leaves out nothing for the reader to guess. · 4 years, 6 months ago

Why does the last row has to be constant? · 4 years, 6 months ago

It is given that the polynomial is of order 8, and there are eight rows in the difference table that are the differences.

n rows of differences means that the polynomial is of order n, so eight rows is that maximum an 8th degree polynomial can have. · 4 years, 6 months ago

I've used exactly this method, extending the finite difference table. The table allows to find the general term and can be easily extended forward or backward indefinitely. · 4 years, 6 months ago

Reason for keeping the last row as constant??? · 4 years, 6 months ago

It is given that the polynomial is of order 8, and there are eight rows in the difference table that are the differences.

n rows of differences means that the polynomial is of order n, so eight rows is that maximum an 8th degree polynomial can have. · 4 years, 6 months ago

i consider the polynomial is f(x) = a.x(x-1)(x-2)......(x-7) + b.x(x-1)(x-2)....(x-6) + c.x(x-1)(x-2)...(x-5) + ........f.x(x-1)(x-2) + g.x(x-1) + h.x + i . this is a polynomial of degree 8. now putting x =0 we get i=2^0 = 1. again putting x=1 we get h+1=2^1 or, h=1 . again putting x= 2,3,....8 we can easily find out the value of a,b,...g. we get i = 1, h =1/1 =1, g=1/12 =1/2 ,f =1/123 =1/6 ,......., a = 1/123.....*8 . now putting x=9 we get f(x)= 511 . · 4 years, 6 months ago

Remarks have been added. Congrats to Ryan! Staff · 4 years, 6 months ago

Lagrange interpolation would be tedious in this case ...... your first method is mathematically solid and more feasible in my opinion · 4 years, 6 months ago

Do we only discuss one question per week for the featured solution? · 4 years, 6 months ago

Yes. You can look up previous discussions through the tag featured solutions.

It is difficult to get a question where people submit such varying viewpoints, or solutions in which they seem correct but are actually being wrong. Bear in mind that only students who have submitted the correct numerical answer may be chosen to submit a solution, so this already removes solutions which are just completely wrong. Staff · 4 years, 6 months ago

But How do you do $${0 \choose 8}$$ for $$f(0)$$? Yours is a good solution, summing up rows of Pascal's triangle, but wouldn't it involve evaluating $$-8!$$? · 4 years, 5 months ago

How do you justify the claim?

i did this using lagrange interpolation, evaluating $$f(9) = \sum_{i=0}^{8} \bigg(2^i \times \prod_{j=0, j \neq i}^{8} \frac{9-j}{i-j} \bigg)$$

I noticed that this was equal to $$\sum_{i=0}^{8} (-2)^i \times \frac{9}{9-i} \times {8 \choose i}$$

How do you convert this into what you claim? · 4 years, 6 months ago

I'm intentionally avoiding Lagrange Interpolation to calculate the polynomial, which merely provides the formula. I do not care what the coefficients are, and they can get pretty ugly.

My claim is to consider the polynomial $$g(x) = \sum_{i=0}^8 { x \choose i}$$. [Do you understand how this is a polynomial?] Then, to establish that this is the degree 8 polynomial that we want, we see that $$g(x)$$ has degree 8, and $$g(n) = f(n)$$ for $$n = 0$$ to 8 (pretty obvious), so it agrees on 9 values, hence $$g(x) = f(x)$$. [This follows because $$g(x) - f(x)$$ is a degree at most 8 polynomial with 9 roots, hence must be the zero polynomial.] Staff · 4 years, 6 months ago

I would say that since 2^n - 2^(n-1) = 2^(n-1), its fairly obvious that the sequences of differences will be the same, and since we were given 9 terms and told that the polynomial is of the 8th degree, then it follows that the 8th difference sequence will be equal to one 1 (given the number of terms) So instead of following by 2, it would follow by 1 so the next term will be (2^n) -1. In other words I see no need to construct the table! · 4 years, 6 months ago

let the polynomial be ax^8+ bx^7+..........gx^2+ hx+ k We insert x=0 and find the value of k as 1 since 2^0=1( for 0 to 8 the fuction is 2^x) Next,we differentiate the above polynomial on both sides. Hence, we get 8ax^7+ 7bx^6.......+2gx+h= 2^x ln2. Now put x=0 on both LHS and RHS and we will get the value of h. If we go on doing this we get the constants as (ln2)^n/n!....When we insert them back into the above equation and put x=9,we do not get 511..Can anyone tell me what is wrong with this solution? Thanks. · 4 years, 6 months ago

The polynomial is only equal to $$2^x$$ on the integers from 0 to 8, not on the interval $$[0,8]$$. (As a matter of fact, that would impossible for any polynomial.) · 4 years, 6 months ago

In solution B why the last rowto be kept constant ¿¿¿¿¿¿¿¿?????????? No proper solution · 4 years, 6 months ago

If $$g(x)$$ is any non-constant polynomial, then the degree of the polynomial $$h(x)=g(x+1)-g(x)$$ will be one less than the degree of $$g(x)$$. · 4 years, 6 months ago

i just want to ask why differentiation of e^4x which is 4*e^4x greater than it as differentiation is breaking down in smaller parts · 4 years, 6 months ago

sir the second explanation of taking a polynomial is like the way i thought but can't we keep the same polynomial to get the values and predict what is taking place....... · 4 years, 6 months ago

I don't think that u can. That process will be very lengthy. Look at the simplicity yet usefullness of solution B. · 4 years, 6 months ago

Solution C - 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.

[Note: Induction was listed as the Key Technique.] Staff · 4 years, 6 months ago

"We now hypothesize that f(9) in the original problem follows our formula"

Proof?? · 4 years, 6 months ago

Induction? · 4 years, 6 months ago

I'm having trouble seeing how induction would work here, since we're adding a variable to each of the original equations AND adding another equation to the system as the degree of the polynomial increases. · 4 years, 6 months ago

Sir how can we say that this formula works for 4,5,6,7,8 degree polynomial , obviously checking like this will be very lengthy, so i think this doesn't prove that f(9)=511 · 4 years, 6 months ago

you cannot rely upon the pattern as you need to check for other degrees as well. we cannot say that watching the pattern gives us a definite answer. you have to check it for other degrees as well including degree 8. so, this is a bad solution. · 4 years, 6 months ago

How you are sure that the pattern working for ,2,3,4 will also work on 9 also You should state the reason or you should prove that f(x) of n degree will give f(n+1)=2^(n+1)-1 · 4 years, 6 months ago

Solution A - $$f(9)=\sum(2^i)$$ for $$i=0$$ to $$8$$. Hence, we have $$f(9) = 2^9 -1=511$$. Staff · 4 years, 6 months ago

Why? · 4 years, 6 months ago

It does follow from the finite difference table in Solution B, but other than that I have no idea. · 4 years, 6 months ago

how can you say so as this is a different solution and has nothing to do with solution- B · 4 years, 6 months ago