Proving a property on a sequence.

Question

I need an hint on how I can prove/disprove a property that I think it's true about a sequence built in a specific way. Let $p \geq 3$ an integer and $n > p$ another integer. I do the following operations, compute $k_0,r_0$ such that

$$ n = k_0p + r_0 $$

then I define $n_1 = 2k_0 + \min(2,r_0)$, I then compute $k_1,r_1$ such that $$ n_1 = k_1p + r_1 $$

and I define $n_2 = 2k_1 + \min(2,r_1)$. For the generic $i$ e compute $k_i,r_i$ such that

$$ n_i = k_ip+r_i $$

and $n_{i+1} = 2k_i + \min(r_i,2)$, I can easily prove that $n_{i+1} < n_i$, but what I want to prove is that for given $n$ and $p$ there's always an index $j$ such $n_j = 2$. Is there any hint you could give me? The only approach I thought was an induction on $p$ but it is not leading me to anything...

Answer 1

Indeed, if $r_i,k_i\ge0$, then $$n_{i+1}=2k_i+\min\{2,r_i\}\le k_ip+r_i=n_i$$ with equality only for $k_i=0, r_i=2$ (i.e., for $n_i=2$). Hence any such sequence starting at $n_0>2$ will strictly decrease until a term becomes $\le 2$ for the first time, i.e., until for some $i$ we have $n_i>2\ge n_{i+1}$. We want to show that in this case $n_{i+1}=2$. If $k_i=0$, we have $r_i=n_i>2$ and so $n_{i+1}=2\cdot0+\min\{2,r_i\}=2$; and if $k_i>0$, then $2\ge n_{i+1}=2k_i+\min\{2,r_i\}\ge 2k_i\ge 2$ so that we conclude that there is equality throughout and again $n_{i+1}=2$.