We found a recursive formula for the following problem:
For any positive integer $n$, let $b(n)$ be the number of ways that you can write $n$ as a sum using only the numbers 1, 2, and 3 where the order of the sum doesn’t matter.
our recursive formula is $$b(n) = b(n-3)+b(n-2)-b(n-5)+1$$
from the values $$b(0)=1, b(1)=1, b(2)=2, b(3)=3, b(4)=4, b(5)=5, b(6)=7, b(7)=8, b(8)=10, b(9)=12, b(10)=14$$
we are trying to find a non-recursive formula for this sequence, so that we can find the values for $b$ at 2012 through 2017
please also explain HOW to get the formula, as this is for marks.
Best Answer
The conventional way to get a closed form for that recurrence would be first to get rid of the constant term by subtracting the equation for $n-1$ from the one for $n$:
You then need to find the roots of the characteristic polynomial of this equation, $$t^6 - t^5 - t^4 + t^2 + t - 1 $$ I cheated and used Wolfram Alpha for that, but it can also be done by hand in this case because there are many $\pm1$ roots. It factors as $$ (t^3-1)(t^2-1)(t-1) = (t+1)(t-1)^2(t^3-1) = (t+1)(t-1)^3(t-\zeta)(t-\zeta^2) $$ where $\zeta$ is a complex third root of unity. (That $(t^3-1)(t^2-1)(t-1)$ factorization sure looks like it has something to do with the 1,2,3 of your original problem statement, doesn't it?)
So the general solution of the recurrence is $$ b(n) = c_1 + c_2n + c_3n^2 + c_4(-1)^n + c_5\zeta^n + c_6\zeta^{2n} $$ Since the sequence is obviously real, we must have $c_5=c_6$, so this becomes $$ b(n) = c_1 + c_2n + c_3n^2 + c_4(-1)^n + c_5 \cdot\begin{cases} 2 & \text{when }3\mid n \\ -1 & \text{otherwise}\end{cases}$$
You will then need to find the $c_i$s by solving the system of linear equations you get by plugging in 5 known values of $b(n)$. Finally you can plug $n=2012$ and so forth into the formula.
Edit: Oops -- the appropriate condition for the result to be real is not $c_5=c_6$, but $c_5=\overline{c_6}$, and there can be an imaginary part in these constants. It is probably easiest then to subsume $c_1$, $c_5$ and $c_6$ into new (real) constants $k_0$, $k_1$, $k_2$, and write $$ \tag{*} b(n) = c_2n + c_3n^2 + c_4(-1)^n + k_{n\,\bmod\,3}$$ Then six known values of $b(n)$ are necessary to find all of the constants -- and a good thing that, because five values would not have been enough to know from the sample values what the constant term we started out by eliminating from the recurrence was.
Even more edit: Note that the form of $(*)$ makes good geometric sense, since the original problem
simply asks for the number of nonnegative integer solutions to $2x+3y\le n$, or in other words the number of points with integral coordinates in a triangle bounded by the horizontal and vertical axes and a line with slope $-\frac32$. To a first approximation we'd expect this to be $\frac 12 (n/3)(n/2)$, so we ought to have $c_3=\frac{1}{12}$. The other terms are there just to correct for fencepost errors. It is to be expected that there are corrections with period 2 and 3 as the axis intercepts of the hypotenuse sweeps past lattice points. It may be surprising that there is no similar periodic variation in the coefficient of the linear term $c_2n$, but that is probably because $2$ and $3$ are coprime, so the density of lattice points on the hypotenuse is the same for all $n$. It would be a different matter if it had been "using only the numbers 1, 2 and 4", for example. End edits.
If simply finding the values of $b(2012)$ upto $b(2017)$ is all you want, it is probably less work just to program a computer to fill in a table of $b(n)$ upto that number, using your recursive equation to fill in each value based on the ones you have already computed.