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$$

f(0) = 1
f(1) = 2
f(2) = 4
f(3) = 5
f(4) = 7
f(5) = 8
f(6) = 10

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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.