1. [15] For this problem, our lawn consists of a row of $n$ clumps of grass. This row runs in an east-west direction. In our formation, each mobot may be oriented toward the north, south, east, or west. One example of an allowable formation if $n=6$ is symbolized below:
(The mobot on the third clump will move westward, mowing the first three clumps. Each of the last three clumps is mowed by a different mobot.) Here's another allowable formation for $n=6$, considered different from the first:
Compute the number of different allowable formations for any given $n$.
Solution: Let $a$ be the number of clumps mowed by a mobot oriented to go west, and let $b$ be the number of clumps mowed by a mobot oriented to go east. (So in the two examples given, $(a, b)$ would be $(3,0)$ and $(3,1)$, respectively.) We may ask how many allowable formations with a given ordered pair $(a, b)$ there are, and then sum our answers up over all possible ordered pairs $(a, b)$.
Given any particular $(a, b)$, first of all, $a$ and $b$ had better be non-negative integers summing to at most $n$. As long as that's true, there will be $n-a-b$ clumps of grass which are each mowed by a single mobot oriented to go either north or south: there are thus $2^{n-a-b}$ possibilities. So our answer is
$$
\begin{array}{l} 
\sum_{a=0}^{n} \sum_{b=0}^{n-a} 2^{n-a-b}=\sum_{a=0}^{n}\left(2^{n-a}+2^{n-a-1}+\cdots\right.\left.+2^{0}\right)=\sum_{a=0}^{n}\left(2^{n-a+1}-1\right) \\
=-(n+1)+\sum_{a=0}^{n} 2^{n-a+1}=-(n+1)+\left(2^{n+1}+2^{n}+2^{n-1}+\cdots+2^{1}\right) \\
=-(n+1)+\left(2^{n+2}-2\right)=2^{n+2}-n-3 .
\end{array}
$$