1
$\begingroup$

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$

I can't find an identity for this summation :(

To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and inductive hypothesis done, this is just my inductive step

$\endgroup$
9
  • $\begingroup$ Your question is not very clear. Would you perhaps care to elucidate what you mean? $\endgroup$ Mar 30, 2014 at 4:55
  • $\begingroup$ The sum is $2^{i+1}$ by binomial theorem. Why do you need an inequality for this? $\endgroup$ Mar 30, 2014 at 4:57
  • 5
    $\begingroup$ $\sum_{k=0}^{i+1} \binom{i+1}{k} < \infty$. There you go $\endgroup$
    – Rookatu
    Mar 30, 2014 at 4:57
  • $\begingroup$ Clarified my question above $\endgroup$
    – user8722
    Mar 30, 2014 at 5:00
  • 1
    $\begingroup$ Using Pascal's identity, you can split the sum $\sum_{k=0}^{i+1}\binom{i+1}{k}$ into two copies of $\sum_{k=0}^i\binom{i}{k}$. In the induction step, you assume the second sum is $2^i$, this immediately implies the first sum is $2\times2^i = 2^{i+1}$. You should work out the Pascal's identity for the first few $i$, everything will then become obvious. $\endgroup$ Mar 30, 2014 at 5:26

1 Answer 1

1
$\begingroup$

Your problem can be proved without making direct application of the Binomial Theorem itself. Let us consider two disjoint sets $A$ and $B$ and $n$ elements at our disposal. Now the problem is to divide the $n$ elements in the two sets. In how many ways can it be done? The answer is easy.

First analyze the problem as for any one of the $n$ elements there are two possibilities of satisfying the condition, namely , either it goes into $A$ or into $B$. It is easy to see that the total number of ways in this case is indeed $2^n$. Right?

Now analyze the same problem a bit differently. Since the sets are disjoint, if we can analyze all the possible distributions in $A$, it will automatically determine all the possible distribution in $B$ because there is a one-one correspondence between the distributions in $A$ and that in $B$. We can take $0$ elements from $n$ elements, the number of ways of choosing in such a manner being $\binom {n}{0}$. Similarly when we choose $1$ element the number of ways becomes $\binom {n}{1}$ and thus generalizing if we choose $i (\leq n)$ elements the number of ways becomes $\binom {n}{i}$ and since each such choice is mutually exclusive with any other choice the total number of such choices will be $\sum_{i=0}^{n} \binom {n}{i}$. And since the total number of ways must be unique we get $\sum_{i=0}^{n} \binom {n}{i}=2^n$. Hence proved.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.