How to get this sum

Question

I know the answer to this sum is $$\sum_{k=0}^{i+1} \begin{pmatrix} i+1\\ k\end{pmatrix} = 2^{i+1} $$ because of pascals rule but how do I evaluate the sum to get this?

TO clarify I used binomial theorem and pascals rule to show

$$\sum_{k=0}^{i+1} \begin{pmatrix} i+1\\ k\end{pmatrix} = \sum_{k=0}^{i+1} (\begin{pmatrix} i\\ k\end{pmatrix} + \begin{pmatrix}i\\ k-1\end{pmatrix}) = \sum_{k=0}^{i+1} \begin{pmatrix} i\\ k\end{pmatrix} + \sum_{k=0}^{i+1} \begin{pmatrix}i\\ k-1\end{pmatrix}$$ and want to keep evaluating this way to get to $$2^{i+1}$$

Answer 1

First of all, note that for Pascal's rule ${{i+1}\choose k} = {i \choose k} + {i \choose {k-1}}$ to always work, you need to follow the convention that $n \choose k$ equals $0$ when $k < 0$ and when $k > n$. I'll be following this convention.

Look at this sum that you have on the right: $\sum_{k=0}^{i+1} {i \choose k}$. The last summand (when $k = i+1$) is ${i \choose {i+1}}$. According to the convention, this is zero. So we may omit the last summand, and your sum equals to $\sum_{k=0}^i {i \choose k}$.

In the second sum $\sum_{k=0}^{i+1} {i \choose k-1}$ the same thing happens with the first summand. For $k=0$ we have ${i \choose 0-1} = 0$. Omitting the first summand, we get the sum $\sum_{k=1}^{i+1} {i \choose k-1}$. By a change of variable this is the same as $\sum_{k=0}^i {i \choose k}$.

So the whole thing becomes $2 \cdot \sum_{k=0}^i {i \choose k}$. This is the same as what we began with, but instead of $i+1$ we have $i$, and the whole thing is multiplied by $2$.

If you go on doing this, you'll get the chain of equalities $$ \sum_{k=0}^{i+1} {i+1 \choose k} = 2 \cdot \sum_{k=0}^i {i \choose k} = 2 \cdot 2 \cdot \sum_{k=0}^{i-1} {i-1 \choose k} = \ldots = 2^{i+1} \cdot \sum_{k=0}^0 {0 \choose k} = 2^{i+1}. $$

Of course, to formalize this last step properly (the $\ldots$ in the middle), you would have to use induction.

Answer 2

You use the Newton formula for $\left(a+b\right)^{n}$

$2^{i+1}=\left(1+1\right)^{i+1}=\sum_{k=0}^{i+1}\binom{i+1}{k}1^{k}1^{i+1-k}=\sum_{k=0}^{i+1}\binom{i+1}{k}$

Answer 3

Use the binomial expansion formula:-

$$(x+y)^{i+1}={i+1 \choose 0}x^{i+1}y^0+{i+1 \choose 1}x^{i}y^1+{i+1 \choose 2}x^{i-1}y^2+\cdots+{i+1 \choose i+1}x^0y^{i+1}\\=\sum_{k=0}^{i+1}{i+1 \choose k}x^{i+1-k}y^k$$

where

$${a \choose b}=\frac{a!}{b!(a-b)!}$$

To evaluate $2^{i+1}$ simply set $x=y=1$, so you have

$$(1+1)^{i+1}=\sum_{k=0}^{i+1}{i+1 \choose k}$$

In order to show that $2^{i+1}$ is indeed the sum, I think induction is the best approach.

For $i=0$, we have ${1 \choose 0}+{1 \choose 1}=2=2^{0+1}$. Assume that $$\sum_{k=0}^{m+1}{m+1 \choose k}=2^{m+1}$$

We need to show that $$\sum_{k=0}^{m+2}{m+2 \choose k}=2^{m+2}$$

Using the expression for Pascal's formula, we have

$$\sum_{k=0}^{m+2}{m+2 \choose k}=1+\sum_{k=1}^{m+1}\left\{{m+1 \choose k}+{m+1 \choose k-1}\right\}+1$$

Now the second term is

$$\sum_{k=1}^{m+1}\left\{{m+1 \choose k}+{m+1 \choose k-1}\right\}\\=\left(\sum_{k=0}^{m+1}{m+1 \choose k}-1\right)+\left(\sum_{v=0}^{m+1}{m+1 \choose v}-1\right)=2^{m+1}+2^{m+1}-2$$

where we use the change of variable $v=k-1$, and the summations do equal $2^{m+1}$, as we hold this true by assumption.

Thus we have

$$\sum_{k=0}^{m+2}{m+2 \choose k}=1+2^{m+1}+2^{m+1}-2+1=2\cdot2^{m+1}=2^{m+2}$$

Answer 4

If you want a combinatorial approach to evaluate your sum, note that ${i+1} \choose k$ is the number of ways to choose a subset of size $k$ from a set of $i+1$ objects. If you sum from $k=0$ to $k=i+1$ then you get the number of ways to get a subset of any size from a set of size $i+1$. This is equal to $2^{i+1}$, because for each element in the set you have two choices, whether to include the element in the subset or not.

Answer 5

Define $f(i) = \sum_{k=0}^{i+1} {{i+1} \choose k}$. You can use induction to prove the formula $f(i) = 2^{i+1}$ for all $i$. Note the formula is true for $i = 0$. Then for $i \geq 0$, your Pascal expansion shows that the answer $f(i+1)$ satisfies $f(i+1) = f(i) + f(i)$ because the two summations on the right hand side of your Pascal expansion formula are equal to $\sum_{k=0}^{i+1} {{i+1} \choose k} = f(i)$, so you get $f(i+1) = 2*f(i) = 2*2^{i+1} = 2^{i+2}$ so the formula is proved for all $i \geq 0$ by induction.