Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
A sequence of positive integer is defined as follows
- The first term is $1$.
- The next two terms are the next two even numbers $2$, $4$.
- The next three terms are the next three odd numbers $5$, $7$, $9$.
- The next $n$ terms are the next $n$ even numbers if $n$ is even or the next $n$ odd numbers if $n$ is odd.
What is the general term $a_n?$
Please, proofs of all these formulas would be nice
The general term is $$\tag1a_n=2n-\left\lceil \sqrt{2 n}-\frac12\right\rceil.$$ Why? We have $a_{n+1}=a_{n}+2$ unless there is an integer $\ge\frac12 +\sqrt{2n}$ and $<\frac12+\sqrt{2(n+1)}$. We need $a_{n+1}=a_n+1$ iff $n$ is one of the numbers $1, 3, 6, 10, \ldots$, i.e. a number of the form $k \choose 2$. This is accounted for by the ceiling/sqrt term.
Proof: That $a_{n}=a_{n-1}+1$ iff $n-1=\frac{k(k+1)}2$ because of the well-known summation $1+2+3+\cdots+k=\frac{k(k+1)}2$ should be clear. For which $\nu$ does there exist a $k$ such that $\nu-1=\frac{k(k+1)}2$? This is a quadratic in $k$ with solutions $$\tag2k_{1,2}=\frac{-1\pm\sqrt{1+8(\nu-1)}}2=\frac{-1\pm\sqrt{8\nu-7}}2.$$ Thus the $\nu$ with $a_{\nu}=a_{\nu-1}+1$ are characterized by the fact that $8\nu-7$ is a square (of an odd number). In total we have $a_n = 2n-m_n$ where $m_n$ is the number of $\nu\le n$ for which $(2)$ has a positive integer solution $k$. But since there is one $\nu$ (namely $\frac{k(k+1)}2$) for each $k=1, 2, \ldots$, we find that $m_n=\left\lfloor\frac{-1+\sqrt{8n-7}}2\right\rfloor$. This proves a different formula, but it can be simplified to $(1)$ by observing that $\sqrt {2n}-\frac12$ is never an integer (that would make $2n$ the square of an odd integer). Therefore $\lfloor\sqrt{2n}+\frac12\rfloor$ may be used instead of $\lceil\sqrt{2n}-\frac12\rceil$ in $(1)$ (or just round $\sqrt{2n}$ to nearest integer). We have $$\left\lfloor\frac{-1+\sqrt{8n-7}}2\right\rfloor\le\left\lfloor \sqrt{2 n}-\frac12\right\rfloor $$ and inequality can only hold if there is a natural number $r$ such that $$\frac{-1+\sqrt{8n-7}}2<s<\sqrt{2 n}-\frac12$$ i.e. $$\sqrt{8n-7}<2s+1<2\sqrt{2 n}$$ $$8n-7<(2s+1)^2<8 n.$$ The latter is impossible because odd squares are $\equiv 1\pmod 8$.
Therefore, rounding $\left\lfloor\frac{-1+\sqrt{8n-7}}2\right\rfloor$ may be replaced with e.g. $\left\lfloor \sqrt{2 n}-\frac12\right\rfloor$ or (with adjustment of the complete formula by a constant) with $\left\lceil \sqrt{2 n}-\frac12\right\rceil$.
Your sequence is the following one:
Not a general term, but an interesting reformulation of your recursion. Given a(1)=1
$$ a(n):=\begin{cases} a(n-1)+1& \text{if} \,\, a(n-1) \text{ is a square}\\ a(n-1)+2 &\text{otherwise} \end{cases} $$
http://oeis.org/A001614 has a few formulas: $$ a_n = 2n - \left \lfloor \frac{1+ \sqrt{8n-7}}{2} \right\rfloor $$
