Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
There's a lot of theory to be found at Wikipedia. Especially see the sections Solving non-homogeneous recurrence relations and Linear homogeneous recurrence relations with constant coefficients. Note that the general method will have you solving a 6th-degree equation, so it may not be practical here. –  Henning Makholm Nov 11 '12 at 22:03
    
This is A001399 -- in fact the first hit found by searching the On-Line Encyclopedia of Integer Sequences for your known values. It gives the simple formula $b(n)=\operatorname{round}(\frac{(n+3)^2}{12})$. –  Henning Makholm Nov 12 '12 at 23:12
add comment

2 Answers

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$:

   b(n)          = b(n-2) + b(n-3)          - b(n-5)          + 1
-         b(n-1) =          b(n-3) + b(n-4)          - b(n-6) + 1
   -------------------------------------------------------------
   b(n) = b(n-1) + b(n-2)          - b(n-4) - b(n-5) + b(n-6)

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

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.

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.

share|improve this answer
add comment

Write the recurrence as: $$ b(n + 5) = b(n + 3) + b(n + 2) - b(n) + 1 $$ Define the generating function: $$ B(z) = \sum_{n \ge 0} b(n) z^n $$ Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize sums like: \begin{align} \sum_{n \ge 0} b(n + r) z^n &= \frac{B(z) - b(0) - b(1) z - \ldots - b(r - 1) z^{r - 1}}{z^r} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \end{align} to get: $$ \frac{B(z) - b(0) - b(1) z - b(2) z^2 - b(3) z^3 - b(4) z^4}{z^5} = \frac{B(z) - b(0) - b(1) z - b(2) z^2}{z^3} + \frac{B(z) - b(0) - b(1) z}{z^2} - B(z) + \frac{1}{1 - z} $$ Solving and writing as partial fractions: \begin{align} B(z) &= \frac{1}{1 - z - z^2 + z^4 + z^5 - z^6} \\ &= \frac{17}{72} \cdot \frac{1}{1 - z} + \frac{1}{4} \cdot \frac{1}{(1 - z)^2} + \frac{1}{6} \cdot \frac{1}{(1 - z)^3} - \frac{1}{8} \cdot \frac{1}{1 + z} - \frac{2 + z}{9 (1 + z + z^2)} \end{align} The first terms are easy to handle by the generalized binomial theorem, for $m$ a positive integer: $$ (1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k $$ Note that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$.

We are left with (here $\omega = - (1 + \mathrm{i} \sqrt{3}) / 2$ is a cubic root of 1): \begin{align} B_2(z) &= \frac{2 + z}{1 + z + z^2} \\ &= \frac{2 + z}{(1 - \omega z) (1 - \omega^2 z)} \\ &= \frac{1}{1 - \omega z} - \frac{1}{1 - \omega^2 z} \end{align} This is definitely getting ugly...

We could also write: \begin{align} B_2(z) &= \frac{2 + z}{1 + z + z^2} \\ &= \frac{(2 + z) (1 - z)}{1 - z^3} \\ &= \frac{2 - z - z^2}{1 - z^3} \end{align} What $B_2$ contributes to $b(n)$ is the coefficient of $z^n$: \begin{align} [z^n] B_2(z) &= [z^n] \frac{2 - z - z^2}{1 - z^3} \\ &= 2 [z^n] (1 - z^3)^{-1} - [z^{n - 1}] (1 - z^3)^{-1} - [z^{n - 2}] (1 - z^3)^{-1} \\ &= \begin{cases} 2 & \text{if } 3 \mid n \\ -1 & \text{otherwise} \end{cases} \end{align} Splicing all the above together gives a formula for $b(n)$, which can be used to compute the values asked for.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.