Given an integer $ m\geq 2$, and two real numbers $ a,b$ with $ a > 0$ and $ b\neq 0$. The sequence $ \{x_n\}$ is such that $ x_1 = b$ and $ x_{n + 1} = ax^{m}_{n} + b$, $ n = 1,2,...$. Prove that (1)when $ b < 0$ and m is even, the sequence is bounded if and only if $ ab^{m - 1}\geq - 2$; (2)when $ b < 0$ and m is odd, or when $ b > 0$ the sequence is bounded if and only if $ ab^{m - 1}\geq\frac {(m - 1)^{m - 1}}{m^m}$.
Problem
Source: China Western Mathematical Olympiad 2008
Tags: induction, ceiling function, logarithms, algebra proposed, algebra
05.11.2008 13:48
For Part 1: let us divide the whole sequence by b, call it $ {y_n}$. Clearly $ {y_n}$ is bounded iff $ {x_n}$ is bounded. The first few terms of $ {y_n}$ are as follows: $ 1$ $ ab^{m - 1} + 1$ $ ab^{m - 1}(ab^{m - 1} + 1)^m + 1$ ...and so on. Figure out the recursive definition of $ {y_n}$ yourself. ($ \Leftarrow$) Note since $ a > 0$ and $ b < 0$, it follows that $ ab^{m - 1} < 0$. Assuming $ ab^{m - 1}\geq - 2$, then $ - 1 < ab^{m - 1} + 1 < 0$. Then we will prove by induction on $ n$ that every $ y_n$ lies in $ [0,1]$. Base case is $ y_1 = 1$. Inductive step: Assume $ y_n \in [0,1]$. Since $ m \geq 2$, $ (y_n)^m \in [0,1]$ as well. Since $ - 1 < ab^{m - 1} < 0$, $ ab^{m - 1}(y_n)^m \in [ - 1,0]$. So $ y_{n + 1} = ab^{m - 1}(y_n)^m + 1 \in [0,1]$. By mathematical induction it follows that $ {y_n}$ is bounded by $ [0,1]$, and we are done. ($ \Rightarrow$) We will prove the contrapositive. Assume $ ab^{m - 1} < - 2$, then $ ab^{m - 1} + 1 < - 1$. Let us prove by induction that $ y_n < - 1$ for all $ n > 1$. Base case ($ n = 2$) is already on the previous line. Inductive step: Assume $ y_n < - 1$. Since $ m \geq 2$ and $ m$ is even, $ (y_n)^m > 1$. It follows that $ y_{n + 1} = ab^{m - 1}(y_n)^m + 1 < ab^{m - 1} \cdot 1 + 1 < - 1$. By mathematical induction it follows that $ y_n < - 1$ for all $ n > 1$. Now let $ N$ be a negative real number. We will show that there exists $ n \in \mathbb{N}$ such that $ y_n < N$. In fact, just let $ n = \left\lceil \dfrac{\log_{ab^{m - 1} + 1}(N)}{m} \right\rceil$. Easy to check that it works. (This $ n$ is a little too big- it guarantees that $ (y_{n - 1})^m$ will be less than $ N$.) Therefore $ {y_n}$ is unbounded if $ ab^{m - 1} < - 2$. We are finally done! Notes: Maybe we could log the whole sequence! This might give a neater solution but I can't see how to use the $ ab^{m-1} \geq 2$ condition. The above solution is mechanical but immediate, and I guess the latter matters more in a competition. Part 2: Next time perhaps.
17.12.2008 15:34
I guess problem (2) is wrong. try $ m=3, a=3, b=-1$.
16.09.2011 10:18
limsk1 wrote: I guess problem (2) is wrong. try $ m=3, a=3, b=-1$. The Chinese version is"<=",not">="
12.05.2017 17:20
Assuming that (2) means that the sequence is bounded iff \( ab^{m-1} \leq \frac{(m-1)^{m-1}}{m^m} \). Lemma: \( \{ x_n \} \) is bounded iff \( ar^m + b = r \) has a positive real root. Proof: \( (\Leftarrow) \) Let the root be \( \alpha \). Then we show via induction that \( \{ x_n \} \) is bounded above by \( \alpha \). Clearly by definition as \( b < 0 \) and \( \alpha > 0 \), \( x_1 < \alpha \). Suppose \( x_k < \alpha \). Then \( x_{k+1} = ax_k^m + b < a \alpha^m + b = \alpha \), as desired. \(( \Rightarrow) \) Suppose otherwise. Then consider the minimum positive value that \( ar^m + b - r \) can take; call it \( \beta \) for convenience. However, remark then that the difference between two consecutive terms in our sequence, \( x_{k+1} - x_k \) is equal to \( ax_k^m + b - x_k \geq \beta > 0 \), which means that \( \{x_n \} \) is unbounded, contradiction. By the lemma, let us rearrange our equality \( ar^m + b = r \) as \( ar^{m-1} + \frac{b}{r} = 1 \) To finish off, we apply AM-GM (the form of which is motivated by the bound in question) to the aforementioned, namely \( ar^{m-1} + \frac{b}{r} = ar^{m-1} +\underbrace{ \frac{b}{(m-1)r} + ... + \frac{b}{(m-1)r}}_{m - 1 \ \text{times}} \geq m \sqrt[m]{ \frac{ab^{m-1}}{(m-1)^{m-1}}} \), which rearranges to the desired.