gaby131o
2022-09-23
Answered

Algebraic Proof that $\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}={2}^{n}$

You can still ask an expert for help

gerasseltd9

Answered 2022-09-24
Author has **8** answers

Let $g(n)=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}$. Then

$$g(n+1)-g(n)=\sum _{i=0}^{n+1}{\textstyle (}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}-\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}=\sum _{i=0}^{n+1}({\textstyle (}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}-{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )})=\sum _{i=0}^{n+1}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i-1}{\textstyle )}$$

$$=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}=g(n).$$

Here, we use the fact that $(}\genfrac{}{}{0ex}{}{n}{n+1}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{-1}{\textstyle )}=0$, as well as the binomial recurrence $(}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{n}{i-1}{\textstyle )$.

Thus we have $g(n+1)=2g(n)$, with $g(0)=1$. Since $g(n)$ doubles each time $n$ is incremented by $$1$$, we must have

$$g(n)=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}={2}^{n}.$$

$$g(n+1)-g(n)=\sum _{i=0}^{n+1}{\textstyle (}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}-\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}=\sum _{i=0}^{n+1}({\textstyle (}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}-{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )})=\sum _{i=0}^{n+1}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i-1}{\textstyle )}$$

$$=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}=g(n).$$

Here, we use the fact that $(}\genfrac{}{}{0ex}{}{n}{n+1}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{-1}{\textstyle )}=0$, as well as the binomial recurrence $(}\genfrac{}{}{0ex}{}{n+1}{i}{\textstyle )}={\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{n}{i-1}{\textstyle )$.

Thus we have $g(n+1)=2g(n)$, with $g(0)=1$. Since $g(n)$ doubles each time $n$ is incremented by $$1$$, we must have

$$g(n)=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}={2}^{n}.$$

Liam Potter

Answered 2022-09-25
Author has **1** answers

Simply use the binomial formula.

$$(a+b{)}^{n}=\sum _{k=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}{a}^{k}{b}^{n-k}$$

With $a=b=1$ you have your result.

$$(a+b{)}^{n}=\sum _{k=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}{a}^{k}{b}^{n-k}$$

With $a=b=1$ you have your result.

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09

In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?

asked 2022-06-26

Suppose we have 20 balls numbered 1,2,...,20. Each day we pick a single ball randomly.

1) What's the probability of picking all 20 balls in 22 days ?

2) What's the probability of picking only 1and2 in 4 days (Atleast 1 times each) ?

1) What's the probability of picking all 20 balls in 22 days ?

2) What's the probability of picking only 1and2 in 4 days (Atleast 1 times each) ?

asked 2022-06-14

A bus follows its route through nine stations, and contains six passengers. What is the probability that no two passengers will get off at the same station?

asked 2021-09-03

Suppose a class consists of 3 students majoring in Mathematics, 4 students majoring in Chemistry and 4 students majoring in Computer Science. How many arrangements are possible for forming a group of 3 students, if each group should consist at least 2 students majoring in chemistry?

asked 2021-11-13

A student is getting ready to take an important oral examination and is concerned about the possibility of having an “on” day or an “off” day. He figures that if he has an on day, then each of his examiners will pass him, independently of each other, with probability .8, whereas if he has an off day, this probability will be reduced to .4. Suppose that the student will pass the examination if a majority of the examiners pass him. If the student feels that he is twice as likely to have an off day as he is to have an on day, should he request an examination with 3 examiners or with 5 examiners?

asked 2021-12-23

A bag contains 3 red balls and 3 blue balls. 2 balls are selected at random. How do you find the probability of selecting 2 red balls?