# How to derive this formula and provide a proof?

I have a formula that "filters" out values of x where x mod 3 is 0:

$$f(x) := 3\cdot\left\lfloor \frac x2\right\rfloor\, +\,(x\mathrm{\,mod\,} 2)\,+\,1$$

e.g.
f(0) = 1
f(1) = 2
f(2) = 4
f(3) = 5
f(4) = 7
f(5) = 8
f(6) = 10
etc.

I've come up with this formula through intuition, but I'm trying to figure out how to create a proof and also how to derive the solution.

• Do an odd/even case analysis. Actually, cases such as $3k, 3k+1, 3k+2$ may be better – David Peterson Jan 15 '17 at 22:28
• By your example, I guess that your domain is the set of natural numbers. A good approach would be to try proof by induction. – Xaver Jan 15 '17 at 22:28

A recursive definition would be $f(0)=1$ and $$f(x+1)=\begin{cases} f(x)+1 & \text{if 3\nmid f(x)+1}\\[4px] f(x)+2 & \text{if 3\mid f(x)+1} \end{cases}$$

Let's examine your function $f$.

We should have $$0<f(x+1)-f(x)\le2$$ and $f(x+1)-f(x)=2$ if and only if $f(x)+1$ is a multiple of $3$.

We have $$f(x+1)-f(x)= 3\left(\left\lfloor\frac{x+1}{2}\right\rfloor- \left\lfloor\frac{x}{2}\right\rfloor \right)+ ((x+1)\bmod 2)-(x\bmod 2)$$

If $x$ is even, then $\lfloor(x+1)/2\rfloor=\lfloor x/2\rfloor$ and $((x+1)\bmod 2)-(x\bmod 2)=1$, so $f(x+1)-f(x)=1$.

If $x$ is odd, say $x=2k+1$, we have $$3\left(\left\lfloor\frac{2y+2}{2}\right\rfloor- \left\lfloor\frac{2y+1}{2}\right\rfloor \right)=3(y+1)-3y=3$$ and $((x+1)\bmod 2)-(x\bmod 2)=-1$, so $f(x+1)-f(x)=2$.

Now suppose that $f(x)+1$ is a multiple of $3$, so $$3\left\lfloor\frac{x}{2}\right\rfloor+ (x\bmod 2)+1+1=3k$$ This means that $x\bmod2=1$, that is, $x$ is odd. In this case, $f(x+1)=f(x)+2$, as required.