Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Arthur Dec 10 '12 at 12:25

1 Answer 1

up vote 2 down vote accepted
+50

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.

share|improve this answer
    
It explains much about how to test an expression. It explains nothing about how to find an expression. –  Arthur Dec 13 '12 at 0:12
    
@Arthur I disagree. Theorem 1.1 and its proof says a lot about finding such expressions. –  Matthew Conroy Dec 13 '12 at 0:34
1  
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. –  Arthur Dec 13 '12 at 8:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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