Question:

What is the value of {::}^kC_k+{::}^(k+1)C_k+..+{::}^nC_k is:

• {::}^(n+1)C_k
• {::}^(n+1)C_(k+1)
• {::}^(n+1)C_(k-1)
• None

Solution

We have obviously have hacks to solve a question, but it is always better to solve a question properly when practing.

First straight forward approach:

People generally say that we can replace {::}^kC_k with {::}^(k+1)C_(k+1), but ask them why did they think of this approach, many won't reply anything.

If you look here we are trying to add {::}^kC_k+{::}^(k+1)C_k

=1+((k+1)!)/(k!)

=1/(k!) (k!+(k+1)!)

=(k!)/(k!) (k+2)

=(k+2)={::}^(k+2)C_(k+1)

From this you could see the trend which is

{::}^(k+1)C_(k+1)+{::}^(k+1)C_k={::}^(k+2)C_(k+1)

{::}^(k+2)C_(k+1)+{::}^(k+2)C_k={::}^(k+3)C_(k+1)

{::}^(k+3)C_(k+1)+{::}^(k+3)C_k={::}^(k+4)C_(k+1)

This is the reason we substitute {::}^kC_k={::}^(k+1)C_(k+1)

So from this is clear that the answer will be {::}^(n+1)C_(k+1)

Induction approach:

We use an induction on variable n. Here we find the function which is satisfied for n=k and then prove that if this equation is satisfied for some n, then it is true for n+1 also.

Coefficients approach:

If you look closely, you can see that {::}^rC_k is the coefficient of x^k in (1+x)^k.

So the given sum is equal to the sum of coefficients of x^k in (1+x)^k+(1+x)^(k+1)+...+(1+x)^n

This is the sum of coefficients of x^k in =1+(1+x)+(1+x)^2+.....+(1+x)^n

This is the coefficients of x^k in =((1+x)^(k+1)-1)/x

This is the coefficients of x^(k+1) in =(1+x)^(k+1)

={::}^(n+1)C_(k+1)