Find a simple expression for the sum of (k^2) * nCk from k=1 to n and prove your answer.?

Question

I came to the answer that the sum is equal to 2^n * (n+2) C 2.

However, I am clueless on how to prove this.

p.s. "C" means choose (combination)

You're right.. it doesn't work when n = 1.

Answer 1

The answer you gave cannot possibly be right. Let n=1. Then 2^n * (n+2)C2 = 2^1 * 3C2 = 6, but [k=1, n]∑k²*nCk = 1² * 1C1 = 1, and 6≠1.

I'll post a proof of the correct answer just as soon as I figure out what it is.

Edit: after much rumination, and many used pieces of scratch paper, I have found a solution.

[k=1, n]∑(k²nCk) = n(n+1)2^(n-2)

In proving this, I will assume that you are already familiar with the fact that (n+1)Ck = nCk + nC(k-1) and that [k=0, n]∑nCk = 2^n. If not, a good proof of the first is provided in the wikipedia article: http://en.wikipedia.org/wiki/Pascal%27s_rule . The second follows from the fact that this is the sum of the numbers on the nth row of my triangle, and each row has a sum twice that of the row before it (think about how each row is constructed).

Our strategy in this proof will be to find a recurrence relation for each sum, and then solve this relation to obtain a general formula. First we will need to prove a lemma:

[k=0, n]∑knCk = n2^(n-1)

Proof:

First note that [k=0, 0]∑k0Ck = 0*0C0 = 0. Now we find a recurrence relation as follows:

[k=0, n+1]∑k(n+1)Ck
Extract the (n+1)th term:
n+1 + [k=0, n]∑k(n+1)Ck
Expand the binomial coefficient:
n+1 + [k=0, n]∑k(nCk + nC(k-1))
Distribute:
n+1 + [k=0, n]∑knCk + [k=0, n]∑knC(k-1)
Extract the 0th term from the right-hand sum (this term is 0):
n+1 + [k=0, n]∑knCk + [k=1, n]∑knC(k-1)
Change the indices of summation:
n+1 + [k=0, n]∑knCk + [k=0, n-1]∑(k+1)nCk
Since the term we extracted at the beginning is the nth term of the sum on the right, we can merge it into the sum:
[k=0, n]∑knCk + [k=0, n]∑(k+1)nCk
Distribute the k+1 term:
[k=0, n]∑knCk + [k=0, n]∑knCk + [k=0, n]∑nCk
Simplify:
2[k=0, n]∑knCk + [k=0, n]∑nCk
And finally:
2[k=0, n]∑knCk + 2^n

So we are looking for an f that satisfies the recurrence relation:

f(0)=0
f(n+1) = 2f(n) + 2^n

Applying this to itself:

f(n+1) = 2(2f(n-1) + 2^(n-1)) + 2^n = 4f(n-1) + 2*2^n
f(n+1) = 4(2f(n-2) + 2^(n-2)) + 2*2^n = 8f(n-2) + 3*2^n
Extrapolating this pattern further:
f(n+1) = 2^(n+1)f(0) + (n+1)2^n
But f(0)=0, so this is simply:
f(n+1) = (n+1)2^n or f(n) = n2^(n-1)

To ensure our extrapolation is correct, we shall prove it rigorously by induction. First we note that f(0)=0, as it should. To show that n2^(n-1) satisfies f(n+1) = 2f(n) + 2^n in general, we assume it works for some n. Then:

f(n+1) = 2f(n) + 2^n
f(n+1) = 2n2^(n-1) + 2^n
f(n+1) = n2^n + 2^n
f(n+1) = (n+1)2^n

Which is what we get by plugging n+1 into the formula. So it works for all n.

Now having proved this lemma, we proceed to [k=0, n]∑k²nCk (yes, your original formula had [k=1, n]∑k²nCk, however since the k=0 term is zero, including it does not change the sum). We'll use the function g to avoid confusing it with the previous function. Of course g(0)=0. Now we need our recurrence relation:

[k=0, n+1]∑k²(n+1)Ck
Extract the (n+1)th term:
(n+1)² + [k=0, n]∑k²(n+1)Ck
Expand the binomial coefficient and distribute:
(n+1)² + [k=0, n]∑k²(nCk + nC(k-1))
(n+1)² + [k=0, n]∑k²nCk + [k=1, n]∑k²nC(k-1)
Change the indices of summation:
(n+1)² + [k=0, n]∑k²nCk + [k=0, n-1]∑(k+1)²nCk
(n+1)² is the nth term of the sum on the right, so we can merge them:
[k=0, n]∑k²nCk + [k=0, n]∑(k+1)²nCk
Expand the binomial:
[k=0, n]∑k²nCk + [k=0, n]∑(k²+2k+1)nCk
And distribute:
[k=0, n]∑k²nCk + [k=0, n]∑k²nCk + 2[k=0, n]∑knCk + [k=0, n]∑nCk
Employing the formulas for [k=0, n]∑nCk and [k=0, n]∑knCk (the latter of which was proved as our lemma):
2[k=0, n]∑k²nCk + 2n2^(n-1) + 2^n
And simplifying further:
2[k=0, n]∑k²nCk + (n+1)2^n

So g(n+1)=2g(n) + (n+1)2^n. Applying this to itself:

g(n+1) = 2(2g(n-1) + n2^(n-1)) + (n+1)2^n = 4g(n-1) + ((n+1)+n)2^n
g(n+1)=4(2g(n-2) + (n-1)2^(n-2)) + ((n+1)+n)2^n = 8g(n-2) + ((n+1) + n + (n-1))2^n
Extrapolating this pattern further:
g(n+1) = 2^(n+1)g(0) + ([k=1, n+1]∑k)2^n
But since g(0) = 0
g(n+1) = ([k=1, n+1]∑k)2^n
And using Gauss's formula for the sum of the first n numbers:
g(n+1) = ((n+1)(n+2)/2)2^n = (n+1)(n+2)2^(n-1) or g(n) = n(n+1)2^(n-2)

Using induction to formally prove our extrapolation correct, we first note that g(n) gives the correct value for n=0. Suppose it works for some n. Then:

g(n+1) = 2g(n) + (n+1)2^n
g(n+1) = 2n(n+1)2^(n-2) + (n+1)2^n
g(n+1) = n(n+1)2^(n-1) + 2(n+1)2^(n-1)
g(n+1) = (n(n+1) + 2(n+1))2^(n-1)
g(n+1) = (n+2)(n+1)2^(n-1)

Which is what we get by plugging n+1 into the formula. Thus, by induction, the formula [k=0, n]∑k²nCk = n(n+1)2^(n-2) is correct for all n.

And with that, I think I shall go to bed.

-Pascal

Answer 2

This situation has lots of blind alleys, yet one thank you to coach it extremely is to evaluate a rational fraction of the form: a/(an-b) the place n > a > b are integers. Subtracting a million/n from it, we've: a/(an-b) - a million/n = (an - an + b)/(n(an-b)) = b/(an² - bn) the place we replace an² - bn with bn' - c, the place b > c. subsequently, we've a the rest fraction the place b < a, and this technique could be repeated till we are left with a fragment of the form a million/n'', and the algorithmic technique ends with a finite sum of fractions. it's going to be spoke of that for any given rational fraction 0 < x < a million, there's a multiplicity of techniques it is expressed interior the form a million/a + a million/b + a million/c + ..., the place a, b, c... are all distinctive integers. This situation jogs my memory of Turing's Halting situation, in that what we are being asked to do is to coach that if we subtract fractions of the form a million/n successively from the unique rational fraction, the approach will halt at last. it is form of relaxing to objective doing it utilising random fractions, at last it halt with in some situations some fantastically an prolonged way out fractions. Addendum: If for any reason throughout the time of the algorithmic technique we arise with 2 fractions that are alike, we are able to apply amir11elad's approach of changing between the fractions with 2 others, and if that motives yet another tournament, we are able to repeat, till after a finite form of step there will be no extra suits and all of the fractions could be distinctive. Addendum 2: right this is the evidence returned, extra concisely: a million) Subtract fractions of the form a million/n from the rational quantity 0 < x < a million successively (with distinctive n) till we are left with a fragment of the form a/(an-b), the place n > a > b are integers. 2) Subtract a million/n from this fraction, so as that we are left with a fragment of the form b/(bn-c), the place n > b > c are integers. 3) proceed till we are left with the fraction of the form a million/n. in case you have a team of integers a > b > c > ...., at last, you will finally end up with a million. it is why the sequence will continuously be finite. Addendum 3: pay attention ye, Alexey V

Answer 3

Write out a few terms to see what they look like:

= 1*n + 2^2(nC2) + 3^2(nC3) + ....

you can cance out one of the ks each time:

= n + 2(n!/(n-1)!) + 3(n!/(2!(n-3)!) + 4(n!/3!(n-4)!) + ...
k(n!/(k-1)!(n-k)! +...

I'm not sure how that will help...