Why is $\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$

Question

Why is $$\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$$

Thanks.

Answer 1

Using the binomial theorem: $$(x+y)^n=\sum_{k=0}^{n} \binom{n}{k} \cdot x^{k} \cdot y^{n-k}$$ we have the following:

$$\sum_{b=1}^{t-1} \binom{t}{b} \cdot 2^{t-b}=\sum_{b=0}^{t} \binom{t}{b} \cdot 1^{b}\cdot 2^{t-b}-\binom{t}{0} \cdot 1^0 \cdot 2^{t-0}-\binom{t}{t} \cdot 1^{t} \cdot 2^{t-t} \\ =(1+2)^t-\frac{t!}{0!t!}\cdot 1^0 \cdot 2^t-\frac{t!}{t!0!}\cdot 1^t \cdot 2^0=3^t-2^t-1 $$

Answer 2

Expand the right hand side: write $3^t$ as $(2+1)^t$ and use the binomial expansion.

Answer 3

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#66f}{\large\sum_{b = 1}^{t - 1}{t \choose b}2^{t - b}}&= 2^{t}\bracks{-1 + \sum_{b = 0}^{t}{t \choose b}\pars{\half}^{b} - 2^{-t}} = 2^{t}\bracks{-1 + \pars{1 + \half}^{t}- 2^{-t}} \\[3mm]&= 2^{t}\bracks{-1 + \pars{3 \over 2}^{t}- 2^{-t}} =\color{#66f}{\large-2^{t} + 3^{t} - 1} \end{align}

Answer 4

This may be viewed as two ways of counting the number of pairs $(A,B)$ with $A \subseteq B$ and $A \neq \varnothing$ and $A \neq \{1,\dots,t\}$. On the left hand side we condition on size. First, pick your set $A$, the number of ways is $\binom{t}{b}$. Next, pick its superset $B$ which we can do in $2^{t-b}$ ways. On the right hand side, we first consider all pairs $(A,B), A \subseteq B$, including letting $A = \varnothing$ or $\{1,\dots,t\}$. The number of such pairs is $3^t$ which follows from the fact we are picking whether each element of $\{1,2,\dots,t\}$ belongs to $A$, $B \setminus A$ or $B^c$. The $2^t+1$ we subtract are the $2^t$ pairs coming from $A = \varnothing$ and the one pair from $A =\{1,\dots,t\}$.