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