0
$\begingroup$

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.

  • 1
    There's a lot of theory to be found [at Wikipedia](http://en.wikipedia.org/wiki/Recurrence_relation). 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.2012-11-11
  • 0
    This is [A001399](http://oeis.org/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})$.2012-11-12

2 Answers 2