This is a problem I have been stuck with for 3-4 days, I've searched everywhere, did all I could, and still couldn't find the answer.
First of all this problem is a part of a problem set, I've solved all of them and this question remains unsolved, here is the problem set because it may help understanding the problem
- If $f(x)$ is a non-zero problem of degree d, then show that $f(x) - f(x-1)$ gives us a problem with a degree d - 1
- If $f(x) = g(x) + h(x)$ then show that $f(x) - f(x-1) = g(x) - g(x-1) + h(x) - h(x-1)$
- Use the binomial theorem to calculate $\frac{x^{k+1}}{k+1} - \frac{{(x-1)}^{k+1}}{k+1}$
I've solved them all, the solution to the last problem is $$\sum_{p=0}^{k} \frac{1}{p+1} \binom{k}{p} \cdot x^{k-p} \cdot \left(-1\right)^{p}$$
Okay now the problem that I couldn't solve is:
Suppose that for all $i \le k$, one knows a polynomial $f_i$ such that $f_i(x) = x^i$. The last problem gave us $f_i$ for $i = 0, 1,2, 3$ and $4$. Combine your work on this problem in order to show you how to calculate $f_{k+1}$
So here are my solving attempts Let's try getting x^0 which is 1, okay? Since f(x) - f(x-1) give us a polynomial of degree (d - 1) and we want d - 1 to be 0, therefore d must be 1
$$f(x) = ax + b$$ $$f(x-1) = ax - a + b$$ Subtracting we get $a$, we need $a$ to equal $x^0$ and $x^0 = 1$ so $a = 1$ so $$f_0 = x + b $$ If we cancel $b$, we get $x$ which equals $\sum_{i=0}^x i^0$
Now let's try getting $x$, the degree must be $2$ so $$f(x) = ax^2 + bx + c$$ $$f(x-1) = ax^2 - 2ax + a + bx - b + c$$ Subtracting we get $$2ax + a- b$$
And this should be equal $x$, so how do we make it equal $x$? first let's get rid of the constant by setting $a = b$
$$2ax$$
Then the obvious next move is to make $a = 0.5$ to make it equal $x$ So $a = 0.5$ and $b = a = 0.5$ so the polynomial is $\frac{x^2}{2} + \frac{x}{2} + c$ ($c$ is any constant) Let's play with this a bit to get
$$f_1 = \frac{x(x+1)}{2} + c$$ Sounds familiar, right? it is a famous summation, by removing $c$ we get $\sum_{i=0}^x i$
Now let's try getting $x^2$ so the degree must be $3$
$$f(x) = ax^3 + bx^2 + cx + d$$ $$f(x-1) = ax^3 - 3ax^2 + 3ax - a + bx^2 - 2bx + b + cx - c + d$$ Subtracting we get $$3ax^2 - 3ax + a + 2bx - b + c = 3ax^2 + (2b - 3a)x + a + c - b$$ And this should be equal to $x^2$, mhm, so how do we start?
Let's eliminate the constants by setting $b = a + c$ Then eliminate $x^1$ by setting $2b = 3a$ Then set the coefficient of $x^2$ to $1$ by setting $a = \frac{1}{3}$ Consequently $b = 0.5$ and $c = 0.5 - \frac{1}{3} = \frac{1}{6}$ So we have our polynomial $$f_2 = \frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} + d$$ Sounds similiar too, by cancelling $d$, this is equal to the famous $\sum_{i=0}^x i^2$
Now let's get $x^3$ (tired yet? this will be the last one)
$$f(x) = ax^4 + bx^3 + cx^2 + dx + e$$ $$f(x-1) = ax^4 - 4ax^3 + 6ax^2 + 4ax + a + bx^3 - 3bx^2 + 3bx - b + cx^2 - 2cx + c + dx - d + e$$ by Subtracting we get, $$4ax^3 + (3b - 6a)x^2 + (4a - 3b + 2c) + (b + d - (a + c))$$ How to make the above an x^3? I won't go through the steps this time but it will be $a = 0.25$, $b = 0.5$, $c = 0.25$ and $d = 0$ So the polynomial would be $$f_3 = \frac{x^4}{4} + \frac{x^3}{2} + \frac{x^2}{4}$$ Which is you know, equal to $\sum_{i=0}^x i^3$
Okay all of this was fun, we found out how to get the summation of successive $x$, $x^2$ , $x^3$. And we could find out how to get the summation of $x^k$ easily (by finding $f_k$) if $k$ was known, but if $k$ wasn't known, how do I find $f_k$?
This is the part that I couldn't solve in the question
Oh yeah and this question suggests that there is some relation between it and the previous one($\frac{x^{k+1}}{k+1} - \frac{{(x-1)}^{k+1}}{k+1}$), Ok I tried plugging $i = 0, i = 1, i = 2, i = 3$ and $i = 4$. Here are the results which are pretty weird and I don't see any relation to this problem.
$i = 0 : 1$
$i = 1 : x - 0.5$
$i = 2 : x^2 - x + \frac{1}{3}$
$i = 3 : x^3 - 1.5x^2 + x - 0.25$
$i = 4 : x^4 - 2x^3 + 2x^2 - x + 0.2$
Ok so these are my solving attempts, so how do I solve this problem?