Spring 2016, problem 7
Comments
U didnt find the point it changes concavity ..which is 1 ...all positive n ,And a maximum depending on u_0 , sum of odd integers (2n+2)(2n+1)/2=(n+1)(2n+1)
@Samurai. Honestly, I don't quite understand what you're saying. Are you suggesting a variation of the problem? What do you mean by concavity in this context? What does the sum of odd integers up to $n$ have to do with it? Also the formula you're quoting is the sum of all integers up to the odd number $2n + 1$ by the way.
I should edit my comment , the recursive function doesnt reset at 1 , but powers of 2 , i had previously though it wouldbe divided by 2 until it reached 1, but that doesnt always occur for just any even numbers! They have to be 2^k for all k
Like Francois' solution below ..' multiplicative to 2 ' ..mod 2 ..powers of two ect
Sir, I am just writing my steps of proof 1. Consider an odd number a(as defined in the problem),I prooved that if the property holds for all the numbers before a,then it holds for all the numbers after a.(can be prrooved by induction and and some trivial inequalities assuming that it holds for odd numbers less than a) 2. Now, considering an odd number before a, be M, and assuming that for all numbers less than m it holds, then each of the term in the sequence must be within the the sequence 1,3,5...a-2(i.e finite),now as thepossible terms of the sequence is finite,then at least after some steps, there must be repeatation of a number in the sequence, hence it becomes periodic(by pegion hole principle). 3. Now to proove for 1, the same finiteness logic follows, Sir, Is My line of proof alright
Sequence of integers $"u_{n+1}=f(u_n)"$ is periodic iff not injective or bounded;
if all $u_n$ are even we are done, else assume wlog $u_0$ odd;
defining $w_{n+2}=\frac {a+w_n}2,\; w_0=u_0, \; w_1=u_1$;
then by induction $u_n\le w_n\le Max\{a,u_0,u_1\}$, (by $\frac x2\leq a+x$), done.
In fact this sequence is linked to the multiplicative order of 2 modulo a.
If $u_n$ is odd, ${u_n} + a$ is congruent to $u_n$ modulo a but is even.
The sequence ${v_n} = {u_n}$ modulo a contains the $\frac{{{u_0}}}{{{2^r}}}$ modulo a (some repeated 2 times consecutively)
The period which finish by appear in this sequence is linked to the sequence $\frac{{{u_0}}}{{{2^r}}}$ modulo a $0 \le r \lt {\rm{order}}\left( 2 \right)\,\bmod \,a$
If a is a prime number and 2 is a primitive root modulo a, only 2 periods can appear (depending of the choice of $u_0$) $\left( {a,2a} \right)$ and the sequence linked to the $\frac{1}{{{2^r}}}$ modulo a $\left( {0 \le r \lt {\rm{order}}\left( 2 \right)\;\bmod \,a} \right)$.
If a is prime and 2 is not a primitive root modulo a or a is composite, more than 2 periods can appear (depending of the choice of $u_0$).
The numbers appearing in all these periods are $1,2,3,...,a,a + 1,a + 3,a + 5,...,2a$
($\frac{{3a + 1}}{2}$ distinct numbers)
For the first a here are the possible periods
a=3 (a is prime and 2 is a primitive root modulo a)
[1, 4, 2]
[3, 6]
a=5 (a is prime and 2 is a primitive root modulo a)
[1, 6, 3, 8, 4, 2]
[5, 10]
a=7 (a is prime and 2 is not a primitive root modulo a)
[1, 8, 4, 2]
[3, 10, 5, 12, 6]
[7, 14]
a=9 (a is composite)
[1, 10, 5, 14, 7, 16, 8, 4, 2]
[3, 12, 6]
[9, 18]
a=11 (a is prime and 2 is a primitive root modulo a)
[1, 12, 6, 3, 14, 7, 18, 9, 20, 10, 5, 16, 8, 4, 2]
[11, 22]
a=13 (a is prime and 2 is a primitive root modulo a)
[1, 14, 7, 20, 10, 5, 18, 9, 22, 11, 24, 12, 6, 3, 16, 8, 4, 2]
[13, 26]
a=15 (a is composite)
[1, 16, 8, 4, 2]
[3, 18, 9, 24, 12, 6]
[5, 20, 10]
[7, 22, 11, 26, 13, 28, 14]
[15, 30]
If we consider u+a to be ignored as a "duplication" of u, and consider two periods {$u$} is a multiple of {$u'$} as long as we can correspond their terms from a point such that $u_i \equiv c \times u_i '$, the only periods are either {a,2a} or a multiple of the period of 1.
It depends on a ! If a is odd this funky function definitly reduces to 1 after so many steps, since we keep plugging in for u n+1---> (un)/2 . once it is 1 the whole cycle starts again adding 1 to a again which again results in an even value for u n which again gets divided by 2 until the value is 1 . so the authors of this problem might reword it to specify value of a .if a is odd and uo odd , u 1 will start out even and start the above cycle with period ln(u1)/ln(2).
I tried it for different values of a_0 odd or even.if odd , and odd plus an odd (even) Bounces it back divided by 2..which is even until its 2 ( decreases) then it 1 , and so its period is1 .
suppose that u n > a. Then u{n+1} might be larger, but only if u n is odd, and then u{n+1} = a + u n is even, so that u{n+2} = (a + u n)/2 < un. So if u_n > a, then in either one or two steps, the sequence gets smaller.
So we can conclude that, eventually, you will get to a value u n which between 0 and a (inclusive). When that happens, then either u{n+1} is also between 0 and a, or u n is odd, u{n+1} = a + u n is an even number between a and 2a, and u{n+2} = (a + u_n)/2 is between a/2 and a (and therefore also between 0 and a). So all terms past this point are integers between 0 and 2a (inclusive).
For each particular value of a, the "next term" function is a map f from the set of integers between 0 and 2a to the set of integers between 0 and 2a. So if you iterate that function,
x, f(x), f(f(x)), f^3(x), f^4(x), ...
then eventually you are going find a repeated term (since otherwise you have infinitely many integers between 0 and 2a). That means that there are distinct positive integers i and j such that
f^i(x) = f^j(x). Aka periodic
This was composite function approach .same idea as. Taking cases for what the 2 main constants are ---> u_o and a
The basic idea is that for large $u_n$ the sequence tends to decrease until it falls into some fixed bounded range. No matter whether it stays there or goes back up again and falls back consequently it will have to hit some number in this bounded range twice, eventually.
Details:
It is easily checked that if $ u_n > a$ for some $ n$ then $ u_{n+1} \lt u_n$ or $ u_{n+2} \lt u_n$ depending on wether $u_n $ is even or odd (remember that $ a$ is assumed to be odd!).
This is already enough to guarantee that there are infinitely many $ k$ such that $ u_k \leq a$. To see this, assume to the contrary that there exists an $ N$ such that for all $ k > N$ we have $ u_k > a$. Since any set of naturals has a minimum, there exists an index $m$ with $m > N$ such that $u_m \leq u_k$ whenever $k > N$. But we know that either $ u_{m+1} \lt u_n$ or $ u_{m+2} \lt u_m$, which contradicts the minimality of $u_m$.
Now there are only finitely many naturals no greater than $a$. So the sequence has to assume at least one value in this range twice. Periodicity then immediately follows.