How can I solve this recurrent equation?

Question

f[1]  = 5
f[2]  = f[1]  + 3*0
f[3]  = f[2]  + 3*0
f[4]  = f[3]  + 3*0
f[5]  = f[4]  + 3*1
f[6]  = f[5]  + 3*1
f[7]  = f[6]  + 3*1
f[8]  = f[7]  + 3*1
f[9]  = f[8]  + 3*2
f[10] = f[9]  + 3*2
f[11] = f[10] + 3*2
f[12] = f[11] + 3*2
f[13] = f[12] + 3*3
f[14] = f[13] + 3*3
f[15] = f[14] + 3*3
f[16] = f[15] + 3*3
f[17] = f[16] + 3*4
f[18] = f[17] + 3*4
f[19] = f[18] + 3*4
f[20] = f[19] + 3*4
…
f[n] = f[n-1] + 3*...


For $n=1,2,3, \ldots$

The solution should only depend on $n$

f[n] = ?

These are the first $50$ numbers

5     5     5     5     8    11    14    17    23    29    35    41    50    59    68    77    89   101   113   125   140   155   170   185   203   221   239   257   278   299   320   341   365   389   413   437   464   491   518   545   575   605   635   665   698   731   764   797   833   869

EDIT: In case it is useful, I made this algorithm in octave/matlab to generate the sequence.

a = zeros(120,1);
a(1) = 5;
a(2) = 5;
a(3) = 5;
a(4) = 5;
inc = 3;
for i = 1:29
    for j = 1:4
        a(i*4+j) = a(i*4+j-1) + inc;
    end
    inc = inc + 3;
end

Answer 1

You might want to break the problem down into two steps.

Notice that each number in the sequence is two more than a multiple of $3$.

So take a new sequence $g(n)$ defined as

$$ g(n)=\frac{f(n)-2}{3} $$

so that $f(n)=2+3g(n)$.

Looking at $g(n)$ we see that

1. $g(1)=g(2)=g(3)=g(4)=1$
2. $g(n)=n-4+g(n-4)$ for $n>4$

Then you may concentrate your effort in finding a general formula for $g(n)$ from which to arrive at a formula for $f(n)$

Answer 2

$$f_{n+1} = f_{n} + 3 \lfloor n/4\rfloor$$ where $f_1 = 5$. If you are not familiar with the $\lfloor x\rfloor$ notation, search for the floor function.

$$f_{i+1} - f_{i} = 3 \lfloor n/4\rfloor$$ $$\sum_{i=1}^{n}(f_{i+1} -f_i) = f_{n+1}- f_1 = 3\sum_{i=1}^n\lfloor i/4\rfloor$$

Since $f_1 = 5$, we get: $$f_{n+1} = 5 + 3\sum_{i=1}^n\lfloor i/4\rfloor$$

Good chance you can get a simpler form on the sum. I will leave that to you.

Answer 3

The recurrence is $f(n+1)= f(n)+3\left\lfloor\frac{n}{4}\right\rfloor$ with initial condition $f(1)=5$, which leads to $$f(n) = 5+3\sum_{k=0}^{n-1}\left\lfloor\frac{k}{4}\right\rfloor$$

After some simplification considering various cases we get

$$f(n) = 5+3\left\lceil\frac{n(n-4)}{8}\right\rceil$$