Sum up to number $N$ using $1,2$ and $3$ So the question asked was finding out the number of ways(combinations), a given number $N$ can be formed using the sum of $1,2$ or $3$.
(eg)
For $n = 8$, the answer is $10$
The given solution for this is simply
$$\left\lfloor\frac{(N+3)^2}{12}\right\rfloor$$
But I don't understand how this is working ?
 A: One approach to this sort of problem is generating functions. If $f(n)$ is the answer for $n$, then we have the formula:
$$\sum_{n=0}^\infty f(n)x^n =\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3} = \frac{1}{(1-x)^3(1+x)(1+x+x^2)}$$
This in turns lets us see that there must be $a,b,c,d,e,f$ such that:
$$f(n)=an^2 + bn + c + d(-1)^n + ew^n + f\bar w^n$$
Where $w=\frac{-1+\sqrt{-3}}{2}$ is a primitive cube root of unity. We can then compute the first $6$ values, $f(0),f(1),\dots, f(5)$ to solve for $a,b,c,d,e,f$. I suspect it will then becomes clear that $|d(-1)^n + ew^n + f\bar w^n|$ is always negative and less than $\frac{1}{2}$, so that you get $f(n)=\lfloor an^2+bn+c +\frac{1}{2}\rfloor$.
This is the math nerd brute force technique. There might be a more inductive approach.
Wolfram alpha helps us compute the partial fractions:
$$\frac{1}{(1-x)(1-x^2)(1-x^3)} = \\\frac{17}{72}\frac{1}{1-x} +\frac{1}{4}\frac{1}{(1-x)^2} + \frac{1}{6}\frac{1}{(1-x)^3}+\frac{1}{8}\frac{1}{1+x} +\frac{1}{9}\frac{2+x}{1+x+x^2}$$
You then see that $$\frac{2+x}{1+x+x^2} = \frac{2-x-x^2}{1-x^3} = \sum w_n x^n$$ has the property that $w_0=2, w_1=-1, w_2=-1, w_{k+3}=w_k$.
This gives us the terms:
$$f(n) = \frac{17}{72} + \frac{1}{4}(n+1) +\frac{1}{12}(n+1)(n+2) + \frac{1}{8}(-1)^n + \frac{1}{9}w_n$$
$\frac{1}{8}(-1)^n + w_n$ is periodic of degree $6$, and we can easily show that $$|\frac{1}{8}(-1)^n + w_n|\leq \frac{25}{72}<\frac{1}{2}$$
So this gives us that $f(n)$ is the nearest integer to:
$$\frac{17}{72} + \frac{1}{4}(n+1)+\frac{1}{12}(n+1)(n+2)=\frac{n^2+6n+9}{12}-\frac{7}{72}$$
This still doesn't get you quite what you want, but it gets you very close.
