Algebraic Proof that ∑_(i=0)^n (n i)=2^n

gaby131o 2022-09-23 Answered
Algebraic Proof that i = 0 n ( n i ) = 2 n
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

gerasseltd9
Answered 2022-09-24 Author has 8 answers
Let g ( n ) = i = 0 n ( n i ) . Then
g ( n + 1 ) g ( n ) = i = 0 n + 1 ( n + 1 i ) i = 0 n ( n i ) = i = 0 n + 1 ( ( n + 1 i ) ( n i ) ) = i = 0 n + 1 ( n i 1 )
= i = 0 n ( n i ) = g ( n ) .
Here, we use the fact that ( n n + 1 ) = ( n 1 ) = 0, as well as the binomial recurrence ( n + 1 i ) = ( n i ) + ( n i 1 ) .
Thus we have g ( n + 1 ) = 2 g ( n ), with g ( 0 ) = 1. Since g ( n ) doubles each time n is incremented by 1, we must have
g ( n ) = i = 0 n ( n i ) = 2 n .
Did you like this example?
Subscribe for all access
Liam Potter
Answered 2022-09-25 Author has 1 answers
Simply use the binomial formula.
( a + b ) n = k = 0 n ( n k ) a k b n k
With a = b = 1 you have your result.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

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) ?
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?

New questions