Recurrence exercise Been stuck on this question for days... Would appreciate any help :)


*

*Devise a function $p(n)$ such that $p(n)$ is the number of different ways to create postage of $n$ cents using 3-, 4-, and 5-cent stamps.

*Prove that $p(n)$ is monotonic nondecreasing on $\mathbb N$.


I'm getting to a point where I can narrow down how to generate $n$ (For a number $n$, take the set of solutions of $n-3$ and add 3 i.e. $p(n-3)$, but I don't know how I would go about accounting for repetitions.
 A: This post How many distinct ways to climb stairs in 1 or 2 steps at a time? might help you get started.  Think about how you can adapt this method to your problem (you can add 3,4, or 5 cents in the last step).  The additional challenge is that you need to account for the permutations.  For example, if n = 9, you can do 3+3+3,4+5, or 5+4.  But there are only two ways: 3+3+3 and 4+5 if we do not care about the order.
A: For each integer $n$, let $p(n)$ be the number of nonnegative integer triples $(x,y,z)$ such that
$$3x+4y+5z=n$$
Using a generating function approach as in

$\qquad$What's the number of natural solutions of $x_1 + 2x_2 + 3x_3 = n$?

we get the recursion
$$
p(n)=
{\small{\begin{cases}
\text{if}\;n<0,\;\text{then}\\[3.5pt]
\qquad 0\\[2.5pt]
\text{else if}\;n=0,\;\text{then}\\[3.5pt]
\qquad 1\\[.6pt]
\text{else}\\[.4pt]
\qquad p(n-3)+p(n-4)+p(n-5)-p(n-7)-p(n-8)-p(n-9)+p(n-12)\\
\end{cases}
}}
$$
Next we show that $p$ is non-decreasing for $n\ge 1$ . . .

For each positive integer $n$, let 
\begin{align*}
a(n)&=p(n+60)-p(n)\\[4pt]
b(n)&=a(n+1)-a(n)\\[4pt]
c(n)&=b(n+1)-b(n)\\[4pt]
\end{align*}
Applying the recursion as many times as needed (using Maple), we can reduce each of $a(n),b(n),c(n)$ to an integer linear combination of $p(n-1),...p(n-12)$, yielding
\begin{align*}
a(n)&={\large{\langle}}{37, 38, 39, 3, -34, -72, -74, -39, -3, 34, 35, 36}{\large{\rangle}}\cdot \vec{P}\\[4pt]
b(n)&={\large{\langle}}{ 1, 1, 1, 0, -1, -2, -2, -1, 0, 1, 1, 1}{\large{\rangle}}\cdot \vec{P}\\[4pt]
c(n)&={\large{\langle}}{0,0,0,0,0,0,0,0,0,0,0,0}{\large{\rangle}}\cdot \vec{P}\\[4pt]
\end{align*}
for all $n\ge 1$, where $\vec{P}={\large{\langle}}{p(n-1),...,p(n-12)}{\large{\rangle}}$.

By direct evaluation, we get $b(1)=1$.

Since $c(n)=0$ for all $n\ge 1$, we get $b(n)=b(1)=1$ for all $n\ge 1$.

Our goal is to prove $p(n)\le p(n+1)$ for all $n\ge 1$.

Proceed by strong induction on $n$.

By direct evaluation, we get $p(1) \le p(2) \le p(3) \le \cdots \le p(61)$.

Next suppose that for some $n\ge 61$, we have $p(k)\le p(k+1)$ for all positive integers $k < n$.
\begin{align*}
\text{Then}\;\;&b(n-60)=1\\[4pt]
\implies\;&a(n-59)-a(n-60)=1\\[4pt]
\implies\;&\bigl(p(n+1)-p(n-59)\bigr)-\bigl(p(n)-p(n-60)\bigr)=1\\[4pt]
\implies\;&p(n+1)-p(n)=\bigl(p(n-59)-p(n-60)\bigr)+1\\[4pt]
\implies\;&p(n+1)-p(n)\ge 1\\[4pt]
\implies\;&p(n) < p(n+1)\\[4pt]
\implies\;&p(n)\le p(n+1)\\[4pt]
\end{align*}
which completes the induction.

Hence, $p$ is non-decreasing for $n\ge 1$, as was to be shown.
