Elegant Problem 2 (1 Viewer)

[OLDMAN]

Find the sum :nC1 (1^2) + nC2 (2^2)+...+nCn (n^2)

 

[Archman]

heres one, not exactly nice tho..

let sum be S
so S = Sum(nCa(a^2)) for a from 0 to n
2S = Sum(nCa(a^2)+nC(n-a)(n-a)^2)
2S = Sum( nCa(n^2-2an+2a^2))
2S = Sum(nCa * (n^2)) - Sum(nCa * 2a(n-a))
2S = 2^n * n^2 - n*(n-1)*2*Sum((n-2)C(a-1)) .... here, a is from 1 to n-1 as the terms of nC0*2*0*n and nCn*2*n*0 are both 0
2S = 2^n*n^2 - n*(n-1)*2*2^(n-2)
S=2^(n-1)*n^2-n*(n-1)*2^(n-2)
S=2^(n-2)*n*(2n-n+1)
S=2^(n-2)*n*(n+1)

hmm.. i would like to see a combinatorial solution tho..

 

[underthesun]

First I considered the expansion of

(1 + x)ⁿ = ⁿC₀ + ⁿC₁x + ... + ⁿC_nxⁿ

I differentiated both side with respect to x, and got
n(1+x)ⁿ = ⁿC₁ + 2ⁿC₂x + ... + nⁿC_nx^n-1

I multiplied both side by x, and got
nx(1+x)ⁿ = ⁿC₁x + 2ⁿC₂x² + ... + nⁿC_nxⁿ

then I differentiated both side :
LHS = ^d/_dxnx(1+x)ⁿ

= n(1+x)^n-1 + nx(n-1)(1+x)^n-2

now:

RHS = ^d/_dx (ⁿC₁x + 2ⁿC₂x² + ... + nⁿC_nxⁿ)

= ⁿC₁ + (2²)ⁿC₂x + ... + (n²)ⁿC_nx^n-1

and LHS = RHS still.

if we let x = 1, RHS is the expression at the beginning (ie the question). Hence, the sum of the expression = LHS when x =1

LHS simplifies to, when we sub x = 1 :

= (n² + n)(1+x)^n-2

which is the required sum.

damn.. I actually went checking Tk / Tk+1 ratio for one hour (had no idea what to do) before I finally realised that to get the answer you have to do differentiation tricks..

 

[Archman]

ha, thats a lot nicer. Looks like calculus is sometimes useful in combinatorics too.

 

[underthesun]

oiy, what's combinatorics?

 

[Archman]

umm.. stuff that involves combinations and permutations etc.

 

[underthesun]

oh ok.

btw so far, the only use of calculus in binomials is for proving (1 + x)ⁿ derivatives / integrals patterns, where you have 1nc1 + 2nc2 + 3nc3 or nc1 / 1 + nc2 / 2 etc..

 

[OLDMAN]

underthesun: nice solid approach again.
Archman: don't self efface, a good solution displaying some fancy combination algebraic footwork.