Is this an identity?

The supposed identity comes from counting the same thing two different ways. Namely, how many combinations are there of putting n distinct objects into two distinct bags if we can put each object in the first bag, in the second bag, or neither.

First way: It is a number of lists of n numbers each being 0,1, or 2 - meaning we put the object into first bag, second bag or neither - giving us $3^n$ combinations.

Second way: We can divide the number of combinations into n cases where we put k objects into first or second bag - this can be done in $2^k$ ways. And for each case we can choose the k objects from n objects in $\binom{n}{k}$ ways.

$$\sum_{k=0}^n \binom{n}{k}2^k = 3^n$$




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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