Curve Fitness Training

Algebra Level 5

If $f(x)$ is the polynomial of degree $\leq 100$ with $f(n)=n^2 2^n$ for all integers $n=1, 2, 3 ,\ldots,101$ , find $f(0)$ .

The answer is 40602.

3 solutions

Chan Lye Lee
Apr 3, 2016

Note that $f(x)=\sum_{r=0}^{100}\left(8r^2+4r+2 \right) {x-1 \choose r}$ fulfill the conditions. Now $f(0)=\sum_{r=0}^{100}\left(8r^2+4r+2 \right) {-1 \choose r}=40602$ Note that ${-1 \choose r}=(-1)^r$ .

Good idea! Just use the binomial sums . Maybe I was over-thinking it ;)

Otto Bretscher - 5 years, 2 months ago

Can you explain further where the expression for $f(x)$ comes from?

Ryan Tamburrino - 5 years, 2 months ago

I'm pretty sure it comes from newton forward differences

Vikram Sarkar - 10 months ago

Mark Hennings
Apr 3, 2016

Now $\sum_{k=0}^{101} \binom{101}{k} (-1)^{101-k} f(k) \; = \; 0$ since $f$ has degree at most 100, so we have $\begin{array}{rcl} f(0) & = & \displaystyle \sum_{k=1}^{101}\binom{101}{k}(-1)^{101-k} f(k) \; = \; \sum_{k=1}^{101}\binom{101}{k}(-1)^{101-k}k^2 2^k \\ & = & \displaystyle 202\sum_{k=0}^{100}\binom{100}{k}(-1)^{100-k}(k+1)2^k \; = \; 202[200(2-1)^{99} +(2-1)^{100}]\\ &= & \boxed{40602}\end{array}$

Can you enlighten me on the first equation? I have no idea at all how we can get it. Thanks.

Chan Lye Lee - 5 years, 2 months ago

The number of surjective (onto) functions from a set with $m$ elements to a set with $n$ elements is (by the Inclusion-Exclusion Principle) $\sum_{k=0}^n \binom{n}{k}(-1)^k (n-k)^m \; = \; \sum_{k=0}^n \binom{n}{k}(-1)^{n-k} k^m$ This is equal to $0$ if $m < n$ . Thus, if $f(x) = a_0 + a_1x + \cdots + a_m x^m$ is a polynomial with degree $m < n$ , then $\begin{array}{rcl} \displaystyle \sum_{k=0}^n \binom{n}{k}(-1)^{n-k} f(k) & = &\displaystyle \sum_{j=0}^m a_j \sum_{k=0}^n \binom{n}{k}(-1)^{n-k} k^j \\ & = & \displaystyle \sum_{j=0}^m a_j \times 0 \; =\; 0 \;. \end{array}$

Mark Hennings - 5 years, 2 months ago

If you are familiar with method of differences , the expression simply states that

For a degree 100 polynomial, the 101th difference is equal to 0.

Calvin Lin Staff - 5 years, 2 months ago

Otto Bretscher
Apr 4, 2016

Here is the solution I had in mind.

From combinatorics we know that $\sum_{k=1}^{n}(-1)^k{n \choose k}k^22^k=(-1)^n 2n(2n-1)$ . For $n=101$ this gives $f(0)=-\sum_{k=1}^{n}(-1)^k{n \choose k}f(k)=-\sum_{k=1}^{n}(-1)^k{n \choose k}k^2 2^k=202\times 201=\boxed{40602}$ .

For the first step, see the formula I used here .

Curve Fitness Training

The answer is 40602.

3 solutions

0 pending reports