Originally Posted by

**bethh** Suppose that 1 is less than or equal to k which is less than n. Prove that the part k occurs a total of (n-k+3)2^(n-k-2) times among all the 2^(n-1) compositions of n.

The teacher gave a hint to use the balls and walls technique, fix a part of size 2 and then count the number of ways to complete the composition. Then use this to prove the general k case.

I'm confused as how to get the number of compositions from the balls and walls technique and then how to go on for the general case. Any help would be appreciated. Thanks.