Combinatorics-number of permutations of $m$ A's and at most $n$ B's Prove that the number of permutations of $m$ A's and at most $n$ B's equals $\dbinom{m+n+1}{m+1}$.
I'm not sure how to even start this problem.

By summing all possibilities of $n$, we get that the number of permutations $P_n$ satisfies
$$P_n = \binom{m+n}{n} + \binom{m+(n-1)}{(n-1)} + \ldots + \binom{m+0}{0} = \sum_{i=0}^n \binom{m + i}{i}$$
Note that
$$\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$$
Repeatedly applying this to the last term, we get
$$\begin{array}{rcl}
\binom{a}{b} &=& \binom{a-1}{b} + \binom{a-1}{b-1} \\
 &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-2}{b-2} \\
 &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-3}{b-3} \\
 &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-4}{b-3} + \ldots \\
 &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-4}{b-3} + \ldots + \binom{a-b-1}{0} \\
 &=& \sum_{i=0}^b \binom{a-b-1+i}{i}
\end{array}$$
Substituting $b$ by $a-b$ we similarly get
$$\binom{a}{a-b} = \sum_{i=0}^{a-b} \binom{b-1+i}{i}$$
Replacing $b = m + 1$ and $a = n + m + 1$ we thus get
$$\binom{n + m + 1}{n} = \sum_{i=0}^{n} \binom{m+i}{i} = P_n$$
