6

Given a positive integer $k$, let $a_1=1$ and $a_{n+1}=\frac{a_n(a_n+n+k)}{n+1}, \forall n \geq 1$. The sequence terminates when a term is not an integer. I'd like to ask whether for all $k$, the sequence will always terminate?

Vepir
  • 12,516
Hang Wu
  • 1,576
  • 5
    Please rephrase the title, it is very ambiguous – Dhanvi Sreenivasan Dec 24 '19 at 09:54
  • What have you tried? Starting out, $a_2=1+k/2$ implies $k$ must be even for $a_2$ to be an integer. Trying $k=2$ in following terms, the sequence grows very fast and it seems it will never terminate. – Vepir Dec 24 '19 at 11:22
  • I have tried brute force to check, but for many values of $k$, the sequences grow so rapidly that I cannot check the condition easily. – Hang Wu Dec 24 '19 at 11:37

1 Answers1

4

Not an answer, but an observation of a possible closed form, which may or may not be useful.

If $k$ is not even, the sequence terminates at $n=2$ since $a_2=1+k/2$.

Hence, assume that $k$ is even $k=2m,m\in\mathbb N$ from now on:

$$ a_{n}=\frac{a_{n-1}(a_{n-1}+n+2m-1)}{n},a_1=1. $$

For $n=1,2,3$ we have $a_n=1,(1+m),(1+m)^2$. For $n\ge4$, we have a closed form:

$$ a_n=(1+m)^2\frac{\prod_{q=4}^{n}P_q(m)}{\prod_{q=4}^{n} q^{2^{n - q}}} $$

Where $P_q(m)$ are degree $2^{q-3}$ polynomials, whose closed form I haven't found:

P_4(m) = 4+4 m+m^2
P_5(m) = 20+20 m+13 m^2+6 m^3+m^4
P_6(m) = 480+480 m+552 m^2+560 m^3+385 m^4+188 m^5+62 m^6+12 m^7+m^8
P_7(m) = 268800+268800 m+462720 m^2+755200 m^3+968304 m^4+1031520 m^5+923760 m^6+695072 m^7+437393 m^8+228248 m^9+97628 m^10+33672 m^11+9126 m^12+1864 m^13+268 m^14+24 m^15+m^16
P_8(m) = 82575360000+82575360000 m+193757184000 m^2+445218816000 m^3+859568947200 m^4+1461969715200 m^5+2225537781760 m^6+3056330956800 m^7+3805161206016 m^8+4307812899840 m^9+4442780243200 m^10+4179035063296 m^11+3587766859744 m^12+2811942207424 m^13+2011414335328 m^14+1311991731008 m^15+779194844129 m^16+420459425712 m^17+205571845944 m^18+90753700816 m^19+36023470076 m^20+12790205744 m^21+4036272008 m^22+1123264464 m^23+272972390 m^24+57212560 m^25+10177544 m^26+1504496 m^27+179548 m^28+16592 m^29+1112 m^30+48 m^31+m^32
P_9(m) = 7671026339020800000000+7671026339020800000000 m+23113532933406720000000 m^2+69358863148646400000000 m^3+181730645536407552000000 m^4+432555324793159680000000 m^5+949326200107853414400000 m^6+1937457161937145036800000 m^7+3698229470022755942400000 m^8+6629458364228047994880000 m^9+11194619325883845967872000 m^10+17849423468477898817536000 m^11+26925814835234794897408000 m^12+38490878951551146550886400 m^13+52216436054882258591416320 m^14+67305716890148955016396800 m^15+82519005618270199022944256 m^16+96317902101878716497920000 m^17+107112591554945344158433280 m^18+113559753558799360762314752 m^19+114835014065179880619982848 m^20+110804339831534161038901248 m^21+102045621542362432535437312 m^22+89716032629778431338921984 m^23+75306149179780436432840192 m^24+60351528507401658860480512 m^25+46176823042397344755454464 m^26+33727709642654821496342528 m^27+23512273651564620608168896 m^28+15639902493256622240854912 m^29+9923387411824565155387584 m^30+6003363164824765445687936 m^31+3461200203000481641804481 m^32+1900684707363531196375392 m^33+993486934890764213127280 m^34+493926415825156880978592 m^35+233372292082453014814648 m^36+104693371859099408241888 m^37+44547322940611223917776 m^38+17957922152221760565280 m^39+6849632573147007030236 m^40+2468535202863979750880 m^41+839245565270792359024 m^42+268693922784075216928 m^43+80854072928946499592 m^44+22818160069793674336 m^45+6024799036325022928 m^46+1484254891811797664 m^47+340134464562300038 m^48+72254882275851808 m^49+14172626844647120 m^50+2555323035617760 m^51+421308814181640 m^52+63138468403360 m^53+8539761673200 m^54+1033682727520 m^55+110835887964 m^56+10395589280 m^57+839395920 m^58+57146208 m^59+3188472 m^60+139936 m^61+4528 m^62+96 m^63+m^64
...

It looks like $m=1$ will always be an integer ($k=2$ is a counterexample to your question), but I haven't been able to prove this.

Vepir
  • 12,516
  • Yes. I find it quite hard (maybe impossible) to find a general closed form solution, not to mention how to prove whether it terminates. – Hang Wu Dec 24 '19 at 15:26
  • Those are some pretty big powers of $q$ down there in the denominator. At first glance it seems very unlikely that all the enumerators are divisible by it. Is there some weird conspiracy going on in the enumerator? – Vincent Dec 24 '19 at 15:34
  • 2
    @Vincent It is hard to say. The $m$ values that are integers for all $n\le 30$ are: $1,3,5,8,13,14,\dots$ but this does not necessarily mean any of them will not terminate. The $m=15$ terminates at $n=29$ for example. Specially for $m=1$, I've checked terms $n\le 38$, and they all are integers. The $a_{38}$ had over five billion digits ($5,577,665,364$ digits). – Vepir Dec 24 '19 at 16:35