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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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

Calvin Lin Staff - 8 years, 4 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.

Ahaan Rungta - 8 years, 4 months ago

very good ...after knowing the solution,everything in the universe looks nice and leaves out nothing for the reader to guess.

Chitres Guria - 8 years, 4 months ago

Why does the last row has to be constant?

Yong See Foo - 8 years, 4 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.

Danny He - 8 years, 4 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.

Silvio Sergio - 8 years, 4 months ago

Reason for keeping the last row as constant???

Abhishek Anand - 8 years, 4 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 .

Titas Saha - 8 years, 4 months ago

Do we only discuss one question per week for the featured solution?

Aldrian Obaja - 8 years, 4 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.

Remarks have been added. Congrats to Ryan!

Lagrange interpolation would be tedious in this case ...... your first method is mathematically solid and more feasible in my opinion

Jaydutt Kulkarni - 8 years, 3 months ago

In solution B why the last rowto be kept constant ¿¿¿¿¿¿¿¿?????????? No proper solution

chhavi kansal - 8 years, 4 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)$ .

Peter Byers - 8 years, 4 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.

Karan Jhanwer - 8 years, 4 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.)

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!

Maher El Ghor - 8 years, 4 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?

Harshit Kapur - 8 years, 3 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.]

Calvin Lin Staff - 8 years, 3 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!$ ?

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

I don't think that u can. That process will be very lengthy. Look at the simplicity yet usefullness of solution B.

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

Yash Goyal - 8 years, 4 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.]

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

Proof??

Ryan Soedjak - 8 years, 4 months ago

Induction?

Zi Song Yeoh - 8 years, 4 months ago

@Zi Song Yeoh – 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.

David Altizio - 8 years, 4 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

Arihant Jain - 8 years, 4 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.

Brilliant Kumar - 8 years, 4 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

Solution A - $f(9)=\sum(2^i)$ for $i=0$ to $8$ . Hence, we have $f(9) = 2^9 -1=511$ .

Why?

Patryk Lipski - 8 years, 4 months ago

It does follow from the finite difference table in Solution B, but other than that I have no idea.

how can you say so as this is a different solution and has nothing to do with solution- B

Why you have summed the range of funtion from 0 t0 8 to get f(9)

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$