# Is this an identity (involving binomial coefficients)?

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$$

• – ComptonScattering Oct 24 '16 at 12:10
• Use that with $3^n = (1+2)^n$. – Daniel Fischer Oct 24 '16 at 12:11

$$3^n=(2+1)^n=\sum_{k=0}^n\binom{n}{k}2^k1^{n-k}=\sum_{k=0}^n\binom{n}{k}2^k$$