What is the relation in this sequence

Question

I was attending a coding competition and this question came up

There is a box containing n chocolates. You can either take 1 chocolate or 3 chocolates at a time until its empty. So in total how many ways you can empty the chocolate for a given n.

Eg: n = 3

ways you can take out is 2 ie:

111
3

ways you can take out when n=4 is 3 ie:

1111
31
13

likewise, I have calculated manually for n=5 -> 4 etc etc..

so the result sequence comes up like 2,3,4,6,9...

I am not able to figure out what kind of relation it has or how do I solve it. I'm not able to figure out what kind of problem it is as well (Permutation, combinations, series?). let me know if I need to post any more details.

Answer 1

I think this problem is one of the problems related to recurrence relation.

Let $a_n$ be the number of ways.

For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.

---

Let's think of the number of ways for $n$. Obviously, it is $a_n$.

If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.

And the number of ways for $n-1$ is $a_{n-1}$.

If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.

And the number of ways for $n-3$ is $a_{n-3}$.

Therefore, for $n \geq 4$,

$$a_n = a_{n-1} + a_{n-3}.$$

The initial value is given as above.

Answer 2

As we can take one or three, we have the recurrence

$$c_n=c_{n-1}+c_{n-3}$$

with the initial condition

$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.

It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.

C= [1, 1, 1]
for n in range(3, 20):
    C.append(C[n-1] + C[n-3])

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872

---

Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, \overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is

$$c_n=ar_0^n+br_1^n+\overline b\overline r_1^n,$$

where constants are determined by the system of equations

$$a+b+\overline b=1,\\ar_0+br_1+\overline b\overline r_1=1,\\ar_0^2+br_1^2+\overline b\overline r_1^2=1.\\$$

As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).

By numerical experimentation, it appears that the simple formula yields exact values in a large range:

$$c_n=[0.6114919919508175\cdot1.465571231876768^n]$$

where the brackets denote rounding to the nearest integer.