6
$\begingroup$

There was this question on one sequence where the expression for the general term contains the floor function. I can clearly see that the floor function is needed for an expression which doesn't burn ones eyes out, but I have no idea how one goes about to construct the explicit formula.

For more examples, there is the sequence A014132 $$ n + \left\lfloor 1/2 + \sqrt{2n} \right\rfloor $$ which contains every integer but the triangular numbers and A000037 $$ n + \left\lfloor1/2 + \sqrt{n-3/4}\right\rfloor $$ which misses exactly the square numbers.

So, let's say you are given the sequence $$ 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25,\ldots $$ of non-Fibonacci numbers during an exam (i.e. you cannot use the OEIS to look it up), and you are told to construct a expression like the ones above for the $n$'th term, how does one think to get to the right answer?

Edit: As a side question, is there some quick way to see which one of the floor and ceiling functions yield the nicest expressions?

New edit: I see that the expression for non-Fibonacci numbers is quite complicated, containing base-$\phi$ logarithms. (I didn't research enough, apparently. I expected it to be on par with the two others.) I'll accept a solution for any of the other sequences, or any similar sequence not discussed here.

$\endgroup$
  • $\begingroup$ Also, I have observed that the expressions for all the sequences discussed here are $\lfloor f(n) + 1/2\rfloor$ or $\lceil f(n) - 1/2\rceil$, so I guess the rounding function is actually the most accurate to use. This shouldn't change what I'm asking for, though. $\endgroup$ – Arthur Dec 10 '12 at 12:25
2
+50
$\begingroup$

Bakir Farhi's paper explains much. In particular, how to generate complementary sequences for sequences of the form $n^a$ and $a^n$, and for the Fibonacci sequence.

$\endgroup$
  • $\begingroup$ It explains much about how to test an expression. It explains nothing about how to find an expression. $\endgroup$ – Arthur Dec 13 '12 at 0:12
  • $\begingroup$ @Arthur I disagree. Theorem 1.1 and its proof says a lot about finding such expressions. $\endgroup$ – Matthew Conroy Dec 13 '12 at 0:34
  • 1
    $\begingroup$ You're right, I didn't see the inversion of $\phi$ there. I thought theorem 1.1 was just a formulation of the usual test, and must have skimmed over it. I will sit down and try it out later today. $\endgroup$ – Arthur Dec 13 '12 at 8:24

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.