Counting the number of ways to use stamps when the available stamps are 1,2, and 3 cents

108 Views Asked by At

My process to solve this:

Letting n = the number of total cents, I will be solving for $a_n$.

So my goal is to find $a_8$, but before this I will have to look at the first three and try to find a pattern.

$a_1 = 1$: 1

$a_2 = 2$: 1+1 2

$a_3 = 4$: 1+1+1 1+2 2+1 3

$a_4$ is where it gets a little complicated so I counted by hand and ended up with 7: 1+1+1+1 1+2+1 1+1+2 1+3 2+1+1 2+2 3+1

This led to a pattern of $a_{n-1}$ of arrangements that start with 1, $a_{n-2}$ arrangements that start with 2 and finally $a_{n-3}$ arrangements that start with 3.

Using this same process for 5 and on, I got to $a_8$ and

$a_8 = a_7 + a_6 + a_5$ = 81.