Combinatorial Identity Question?

consider the following generating function:

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

rewrite (2+x) as [1+(1+x)], and expand f(x) as a series of (1+x),

f(x) = [1+(1+x)]^n (1+x)^2

= sum_k C(n,k) (1+x)^(n-k) (1+x)^2

= sum_k C(n,k) (1+x)^(n-k+2)

= sum_k,m C(n,k) C(n-k+2,m) x^m,

in the last step, we have further expanded (1+x)^(n-k+2).

From this expression, the coeffient of x^3 (i.e., m=3) is collected as

c3 = sum_k C(n,k) C(n-k+2,3) x^3

This is the left hand side.

Now expand (2+x)^n (1+x)^2 directly

The coefficent of x^3,

c3 = 2^(n-1) C(n,1) + 2^(n-2) C(n,2) *2 + 2^(n-3) C(n,3)

= 2^(n-1) n + 2^(n-2) n(n-1)/2! *2 + 2^(n-3) n(n-1)(n-2)/3!

= (n/3)(n + 2)(n + 7) 2^(n-4)

= the right hand side.

Hi Absird,

I have so much work to do today, and Half-Blood Prince's answer is smooth already. But, I happen to like the question and my brain is wanting a combinatorial visualization, so this is just to offer a different perspective:

The left hand-side corresponds to the following process: Let S be a set with n elements. Let a and b be two "special singletons" not in S -- like two people standing by the side. (*) Pick k between 0 and n-1, and pick a subset R of size k from S alone. Now, after having picked R, pick 3 guys T from the remaining elements of S as well as from a and b. I.e. T is chosen from (S U {a,b}) \ R. Now put everybody back, and go again to (*).

Now, about the right hand side, the thing that should be notable is that it looks like there is something that approximately resembles C(n+x,3) multiplied by what is clearly the number of total configurations of k (from 0 to n) elements chosen from n-3 elements (because I already took away a factor of 2). Ok, if things were real clean to begin with, without the a and b etc., this might look a little cleaner but its not perfectly clean, so I'm going to do the next thing which is to consider the cases of a and b's involvement in T.

So first, let's note that all the configurations enumerated by the left hand side and corresponding to the equivalent combinatorial process can be expressed simply as the vector <R,T>. Now, we consider the cases for T:

i) Configurations in which *both* a and b are in T: Then the third guy in T is just chosen from the remainder of S, so this sub-total is:

Sum_{k=0 to n-1} C(n,k)*(n-k) =

(as if we picked the third guy first)

= Sum_{k=0 to n-1} n*C(n-1,k)

= n Sum_{k=0 to n-1} C(n-1,k) = n*(2^(n-1) - 1) = X

ii) Configurations in which either a XOR b are in T: Then the other two guys are picked from the remainder of S, and with similar arrangements to above, we get the total to be:

2*Sum_{k=0 to n-1} C(n,k)*[(n-k)*(n-k-1)]/2 =

(as if we picked the two guys in T from S first)

= n*(n-1)*Sum_{k=0 to n-3} C(n-2,k) = n*(n-1)*(2^(n-2)-1) = Y

iii) Finally, just configurations in which T is a subset of S:

Sum_{k=0 to n-1} C(n,k)C(n-k,3) =

(same idea as in (i) and (ii) you can see how it reduces to this)

= C(n,3) 2^((n-3) - 1) = Z

Now all that remains is to combine C = X+Y+Z and simplify, and that is fairly straightforward unless I made a mistake in +/- some constants...

I am not going to write the full proof because I am pretty busy (must jet) and these combinatorial proofs take a lot longer to write down than they do to think up. Sorry if even what I've got too far is too cumbersome, but I just wanted to point out a different way of thinking about combinatorial identities directly. Cheers...

PS: Thanks, absird, but I know you are pretty skillful yourself. Stamina part... well in the past when I was a student concerned just about "how to prove it somehow" I might not have gone the route of direct but lengthier counting arguments but instead used induction or any set of identities that I'd already seen proven. But now, as an educator it has become more important to me to be able to present the direct "assumptionless" or "elementary" explanation as much as possible (not that it is always straightforward: it depends on the inherent complexity of the combinatorial problem at hand which is an interesting question in itself), especially when such an explanation is somewhat visual. Then again, I'm just starting teaching, so I have yet to learn a lot. :D