Prove that among all the 2^(n−1) compositions of n, the part k occurs a total of (n − k + 3)2^(n−k−2) times

Question

Let 1 ≤ k < n. Prove that among all the 2ⁿ⁻¹compositions of n, the part k occurs a total of (n − k + 3)2^n−k−2 times. For instance, if n = 4 and k = 2, then the part 2 appears once in 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, and twice in 2 + 2, for a total of five times.

Answer 1

Definitions:

Define p(n) = 2^n-1 = the number of compositions of n, for positive integers n>0. 

Define p(0) = 1, representing the empty set. Note: This is not 2^0-1 = 1/2.

Define C(n,k) to be the number of times part k appears in all of the compositions of n. 

We will show:

and then prove: 

C(n,k) = (n − k + 3)2^n−k−2

For example case: n=2, k=1.

C(2,1) = p(0)p(1) + p(1)p(0) = 2

The compositions of n=2 are:

2

1+1

And k=1 appears twice, which proves the base case for formula C(n,k).

Consider the general case for n and k.

Look at how many compositions of n have a part k as the first term in the sum.

n is represented in the next several figures as n horizontal dashes, and the parts that sum to n are separated from each other by a vertical line in the space between 2 dashes. There is no set number of terms in a composition of n other than it is less than or equal to n-k+1. 

There are p(n-k) = 2^n-k-1, n-k ≥ 1, such compositions. These may include another part k in the sum at another location, which will get counted when we look at that location.

There are n-k additional possible locations of k dashes (k-1 spaces) with no vertical lines between them. Each one is shifted one dash to the right of the one before it. 

For example, if the first term is 1 followed by a part k, then the figure looks like:

--- | --- --- ... --- | --- ? --- ? --- ? ... ? ---

part 1 + part k + (n-k-1) dashes that may or may not be split into one or more parts.

This location for part k has p(n-k-1) = 2^n-k-2 possible compositions.

The last possible location of a part k is shown in this figure:

This also has p(n-k) = 2^n-k-1 compositions.

The general location of a part k will have m dashes in front of it and n-k-m dashes after it, where 0 ≤ m ≤ n-k. These locations for part k will have p(m)p(n-k-m) compositions for that location.

For the total number of compositions of n that have a part k, sum all these compositions.

Each m, 0 ≤ m ≤ n-k, provides a term in this sum. (1)

Now the proof that C(n,k) = (n+1-k+3)2n+1-k-2

Given:

p(m) = 2^m-1 for m > 0

p(0) = 1

For 0 < m < n-k, p(m)p(n-k-m) = 2^m-12^n-k-m-1 = 2^n-k-2

To deal with p(0)=1 (when m=0 or m=n-k), remove the first and last terms from the sum in formula (1) for C(n,k):

C(n,k) = p(0)p(n-k)+p(n-k)p(0) + (n-k-1)p(m)p(n-k-m) 

= (1+1)2^n-k-1 + (n-k-1)2^n-k-2 for n-k ≥ 1

=2²2^n-k-2 + (n-k-1)2^n-k-2 for n-k ≥ 1

= (4 + n-k-1)2^n-k-2 for n-k ≥ 1

C(n,k) = (n-k+3)2^n-k-2 for n-k ≥ 1

Proof complete.