Welcome to our community

Be a part of something great, join today!

Find integer sequences

hxthanh

New member
Sep 20, 2013
16
Define $\{a_n\}$ is integer sequences (all term are integers) satisfy condition

$a_n=a_{n-1}+\left\lfloor\dfrac{n^2-2n+2-a_{n-1}}{n}\right\rfloor $ for $n=1,2,...$

*note: $\left\lfloor x\right\rfloor$ is a greatest integer number less than or equal $x$
Find general term of sequences.
 

Amer

Active member
Mar 1, 2012
275
Define $\{a_n\}$ is integer sequences (all term are integers) satisfy condition

$a_n=a_{n-1}+\left\lfloor\dfrac{n^2-2n+2-a_{n-1}}{n}\right\rfloor $ for $n=1,2,...$

*note: $\left\lfloor x\right\rfloor$ is a greatest integer number less than or equal $x$
Find general term of sequences.
is there an initial term ? [tex]a_0[/tex]
 

hxthanh

New member
Sep 20, 2013
16
is there an initial term ? [tex]a_0[/tex]
$a_0$ is'nt importan!
because $a_1=a_0+\left\lfloor\dfrac{1^2-2.1+2-a_0}{1}\right\rfloor=1$
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
Define $\{a_n\}$ is integer sequences (all term are integers) satisfy condition

$a_n=a_{n-1}+\left\lfloor\dfrac{n^2-2n+2-a_{n-1}}{n}\right\rfloor $ for $n=1,2,...$

*note: $\left\lfloor x\right\rfloor$ is a greatest integer number less than or equal $x$
Find general term of sequences.
$a_n = 1 + \left\lfloor\dfrac{(n-1)^2}3\right\rfloor.$ To prove that, use induction, but by establishing three steps at a time rather than the usual one step.

Before starting the proof, notice that $a_n = \left\lfloor\dfrac{n^2-2n+2-a_{n-1} + na_{n-1}}{n}\right\rfloor = \left\lfloor\dfrac{(n-1)(a_{n-1} + n-1) +1}{n}\right\rfloor$. Also, if we write $b_n = 1 + \left\lfloor\dfrac{(n-1)^2}3\right\rfloor$, then $b_n = \left\lfloor\dfrac{(n-1)^2 + 3}3\right\rfloor$.

The inductive hypothesis is that if $n=3k+1$ then $a_{3k+1} = b_{3k+1} = 3k^2+1$, and that furthermore this is still true if the floor signs are omitted. In other words, if $n=3k+1$ then the fractions in the expressions for $a_n$ and $b_n$ are integers, so there is no need to take their fractional parts. This is true for $k=0$.

That hypothesis implies that $$a_{n+1} = a_{3k+2} = \left\lfloor\dfrac{(3k+1)(3k^2+3k+2) +1}{3k+2}\right\rfloor = \left\lfloor\dfrac{9k^3 + 12k^2+9k+3}{3k+2}\right\rfloor = \left\lfloor 3k^2 + 2k + 1 + \tfrac{2k +1}{3k+2}\right\rfloor = 3k^2 + 2k + 1.$$ Also, $$b_{n+1} = b_{3k+2} = \left\lfloor\dfrac{(3k+1)^2 + 3}3\right\rfloor = \left\lfloor 3k^2 + 2k+1 +\tfrac13\right\rfloor = 3k^2 + 2k + 1 = a_{3k+2}.$$

This in turn implies that $$a_{n+2} = a_{3k+3} = \left\lfloor\dfrac{(3k+2)(3k^2+5k+3) +1}{3k+3}\right\rfloor = \left\lfloor\dfrac{9k^3 + 21k^2+19k+7}{3k+3}\right\rfloor = \left\lfloor 3k^2 + 4k + 2 + \tfrac{k +1}{3k+3}\right\rfloor = 3k^2 + 4k + 2.$$ Also, $$b_{n+2} = b_{3k+3} = \left\lfloor\dfrac{(3k+2)^2 + 3}3\right\rfloor = \left\lfloor 3k^2 + 4k+2 +\tfrac13\right\rfloor = 3k^2 + 4k + 2 = a_{3k+3}.$$
This in turn implies that $$a_{n+3} = a_{3k+4} = \left\lfloor\dfrac{(3k+3)(3k^2+7k+5) +1}{3k+4}\right\rfloor = \left\lfloor\dfrac{9k^3 + 30k^2+36k+16}{3k+4}\right\rfloor = 3k^2 + 66k + 4.$$ Also, $$b_{n+3} = b_{3k+4} = \left\lfloor\dfrac{(3k+3)^2 + 3}3\right\rfloor = 3k^2 + 6k + 4 = a_{3k+4}.$$ Notice that the fractions for $a_{n+3}$ and $b_{n+3}$ both had zero remainder on division, and therefore gave integer results without having to take the integer part. Notice also that $3k^2 + 6k + 4 = 3(k+1)^2 + 1$, which completes the inductive step.
 

hxthanh

New member
Sep 20, 2013
16
$a_n = 1 + \left\lfloor\dfrac{(n-1)^2}3\right\rfloor.$
...
very nice solution!

Some similar results

$a_n=1+\left\lceil\dfrac{n(n-2)}{3}\right\rceil$

$a_n=1+(2n-2)\left\lfloor\dfrac{n}{3}\right\rfloor-3\left\lfloor\dfrac{n}{3}\right\rfloor^2$

Also, by induction show that $a_n-a_{n-1}=\left\lfloor\dfrac{2(n-1)}{3}\right\rfloor$