What is the relation in this sequence 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.
 A: 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.
A: 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. 
