IntegerSolution Difficult

Problem - 4329

How many different ways are there to make a payment of $n$ dollars using any number of $\$1$ and $\$2$ bills?


The answer is the coefficient of the $x^n$ term in the expansion of $$\begin{array}{rl} f(x)=&(1+x+x^2 + \cdots)(1+x^2 + x^4 + \cdots) \\ =&\displaystyle\frac{1}{1-x}\cdot\frac{1}{1-x^2} \\ =&\displaystyle\frac{1}{(1-x)^2}\cdot\frac{1}{1+x} \\ =& \displaystyle\frac{1}{2}\left(\frac{1}{(1-x)^2}+\frac{1}{1-x^2}\right) \\ =& \displaystyle\frac{1}{2}\left( (1+2x+3x^2+4x^3+\cdots) \right. \\& + \left.(1+x^2+x^4+x^6+\cdots) \right) \\ =& 1+ x + 2x^2 + 2x^3 + 3x^4 +\cdots \\ =& \displaystyle\sum_{n=0}^{\infty}\left(\left\lfloor{\frac{n}{2}}\right\rfloor+1\right)x^n\end{array}$$

Therefore, the answer is $\boxed{\left(\left\lfloor{\frac{n}{2}}\right\rfloor+1\right)}$ where function $\lfloor{x}\rfloor$ returns the largest integer not exceeding the given real number $x$.

Note the expansion of $\frac{1}{(1-x)^2}$ utilizes the conclusion of # 4284.


report an error