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

gaby131o

gaby131o

Answered question

2022-09-23

Algebraic Proof that i = 0 n ( n i ) = 2 n

Answer & Explanation

gerasseltd9

gerasseltd9

Beginner2022-09-24Added 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 .
Liam Potter

Liam Potter

Beginner2022-09-25Added 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?