The relation holds for n=1 so proceeding by induction:
Unfortunately I have been unable to manipulate this to give the required result. I expect to use the two relations:
Of course I could be on completely the wrong track!
Dec 2nd 2008, 03:54 PM
We also have: since commutes with the identity. ( we define )
However, note that:
Now see the entries on the LHS by using (1) and we are done.
Dec 2nd 2008, 06:12 PM
Okay, now a combinatorial proof.
Consider: note that (check the initial values and the recurrence relation)
Now the RHS of your identity equals
First note that, if a vector satisfies then ( indeed, at most we can have n-1 2s ) (1)
So it is formed by combining a vector of entries, and a complementary one, like this: ( can be 0, or )
Now choose of the first entries to be 2s, the rest of the first n entries are going to be defined as 1s. We can do this in ways. And we have summed so far. So we require . but this can be done in exactly: ways. So if, among the first n entries, we have 2s, we can achieve this in ways.
If we sum all the possible number of 2s among the first n entries ( disjoint cases) we'll have: