Wednesday, 1 February 2012

Generating functions part 3: constant from integration

This passage surrounds the following problem.

Find the general formula for $\sum^{n}_{i=1} i^k$ where k can be any non-negative number.

We know that a sum of polynomial of degree n would give polynomial of degree (n+1) by knowledge similar to integration, so we are not going to find the general formula through k, but through n for any fixed k.

For the first few k many of you should have already recited these:
1) $\sum i^0 = f_0(n) = n$, this is the series 1+1+1+...
2) $\sum i^1 = f_1(n) = \frac{n(n+1)}{2}$, this is the summation of A.S..
3) $\sum i^2 = f_2 (n) = \frac{n(n+1)(2n+1)}{6}$
4) $\sum i^3 = f_3(n) = (\sum i^1)^2 = \frac{n^2(n+1)^2}{4}$

For fixed k we only need to differentiate/integrate w.r.t. n, it seems easy:
$\frac{df_k(n)}{dn}=(\sum i^k)' = k\sum i^{k-1} = kf_{k-1}(n)$.
Yes this is a diff. w.r.t. n (the summation formula is in terms of n, so we differentiate w.r.t. i in the summation sign.), but it looks like it's differentiate w.r.t k.

However, this would be a good news to us because we can link functions of different k together, while smaller k is trivially to compute.

We try to differentiate a few of them:
1) $f'_1(n)=(\frac{n^2+n}{2})'=n+\frac{1}{2}=f_0 (n)+\frac{1}{2}$
2) $f'_2(n)=(\frac{2n^3+3n^2+n}{6})'=n^2+n+\frac{1}{6}=2f_1(n)+\frac{1}{6}$
3) $f'_3(n)=(\frac{n^4+2n^3+n^2}{4})'=n^3+\frac{3}{2}n^2+\frac{1}{2}n=3f_2(n)$

Noticing the varying constant at the last, what happened?

Constant remind us about the constant results from integration, but why we get such a constant from integration, and are there any formula to compute that constant?

In elemental approach we can explain it like this by integration:

$k\int f_k(n) dn=f_{k+1}(n)+C$

Now note that this C depends of the initial value of f(n), now we know that $f_k(1)=1^k=1$, so C is equal to zero because the function does not contain any other constant other than the integration concerning the polynomial.

However, the constant of $f_k(n)$ is not necessarily related to the constant of $f_{k+1}(n)$, then we have to determine the constant again. For constant with non-zero degree, i.e., $Cx,C'x^2$, it's no longer vary along to initial value, so it could be fixed for further integration.

Now $f_0(n)=n+C_0$ where C=0 for k=0. $\int f_0(n)=\frac{n^2+2C_0n}{2}$, by putting $f_k(1)=1$ we have $C_0=\frac{1}{2}$

However, it's extremely hard to generate the general formula of the constant because it's in a special recurrence form.

Let's try the formula for $f_4(n)$:

$f_4(n)=4\int (\frac{n^2(n+1)^2}{4}+C_3)dn=\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}+C_3n+C_4$, putting n=1 gives $n=1-2^{-1}-3^{-1}-5^{-1}=\frac{-1}{30}$. $C_4=0$ for k=4, though it will vary for larger k. Now we get $\sum a^4 = \frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$. Try the first few term which is correct.

Problem to explore:
1) Show that $C_4=0$ and $C_5=\frac{34}{105}$, hence find the formula for k=5,6,7 and try the first few terms.
2) Prove or disprove that $\sum a^{2k+1}$ is divisible by $\sum a$ for all natrual n,k.