Define the sequences $(a_n),(b_n)$ by \begin{align*} & a_n, b_n > 0, \forall n\in\mathbb{N_+} \\ & a_{n+1} = a_n - \frac{1}{1+\sum_{i=1}^n\frac{1}{a_i}} \\ & b_{n+1} = b_n + \frac{1}{1+\sum_{i=1}^n\frac{1}{b_i}} \end{align*}1) If $a_{100}b_{100} = a_{101}b_{101}$, find the value of $a_1-b_1$; 2) If $a_{100} = b_{99}$, determine which is larger between $a_{100}+b_{100}$ and $a_{101}+b_{101}$.
Problem
Source: China MO 2023 Day 1 P1
Tags: algebra, Sequence
29.12.2022 09:25
Now $a_{n+1}(1+\sum\limits_{i=1}^n\frac1{a_i})=a_n(1+\sum\limits_{i=1}^n\frac1{a_i})-1=a_n(1+\sum\limits_{i=1}^{n-1}\frac1{a_i})=\cdots=a_1$ So $\frac{a_1}{a_{n+2}}=1+\sum\limits_{i=1}^{n+1}\frac1{a_i}=1+\sum\limits_{i=1}^n\frac1{a_i}+\frac1{a_{n+1}}=\frac{a_1+1}{a_{n+1}}$ $a_{n+2}=\dfrac{a_1}{a_1+1}a_{n+1}$ Which gives $$\boxed{a_n=\left(\dfrac{a_1}{a_1+1}\right)^n(a_1+1)}$$Similarly we have $b_n=\dfrac{b_1+2n-2}{b_1+2n-3}b_{n-1}$ (1) $\frac{a_1}{a_1+1}=\frac{a_{101}}{a_{100}}=\frac{b_{100}}{b_{101}}=\frac{b_1+199}{b_1+200}\Longrightarrow a_1-b_1=199 $ (2) $a_{100}+b_{100}-a_{101}-b_{101}=\dfrac{a_{100}}{a_1+1}-\dfrac{b_{100}}{b_1+199}=a_{100}\left(\dfrac1{a_1+1}-\dfrac{b_1+198}{(b_1+197)(b_1+199)}\right)$ We will prove $a_1+1<\dfrac{(b_1+197)(b_1+199)}{b_1+198}:=t$ which means $a_{100}+b_{100}>a_{101}+b_{101}$. But this is because \begin{align*} \left(\dfrac{a_1}{a_1+1}\right)^{100}(a_1+1)=a_{100}=b_{99}&=\dfrac{b_1+196}{b_1+195}\cdot\dfrac{b_1+194}{b_1+193}\cdot\cdots\cdot\dfrac{b_1+2}{b_1+1}\cdot b_1\\&=\dfrac{(b_1+197)(b_1+199)}{b_1+198}\cdot\boxed{\dfrac{b_1+198}{b_1+199}\cdot\dfrac{b_1+196}{b_1+197}}\cdot\dfrac{b_1+194}{b_1+195}\cdot\cdots\cdot\dfrac{b_1+2}{b_1+3}\cdot\dfrac{b_1}{b_1+1}\\&<t\cdot\boxed{\left(\dfrac{t-1}{t}\right)^2}\cdot \left(\dfrac{t-1}{t}\right)^{98}\\&=\left(\dfrac{t-1}{t}\right)^{100}t.
29.12.2022 09:45
a22886 wrote: Now $a_{n+1}(1+\sum\limits_{i=1}^n\frac1{a_i})=a_n(1+\sum\limits_{i=1}^n\frac1{a_i})-1=a_n(1+\sum\limits_{i=1}^{n-1}\frac1{a_i})=\cdots=a_1$ So $\frac{a_1}{a_{n+2}}=1+\sum\limits_{i=1}^{n+1}\frac1{a_i}=1+\sum\limits_{i=1}^n\frac1{a_i}+\frac1{a_{n+1}}=\frac{a_1+1}{a_{n+1}}$ $a_{n+2}=\dfrac{a_1}{a_1+1}a_{n+1}$ Which gives $$\boxed{a_n=\left(\dfrac{a_1}{a_1+1}\right)^n(a_1+1)}$$Similarly we have $b_n=\dfrac{b_1+2n-2}{b_1+2n-3}b_{n-1}$ (1) $\frac{a_1}{a_1+1}=\frac{a_{101}}{a_{100}}=\frac{b_{100}}{b_{101}}=\frac{b_1+198}{b_1+199}\Longrightarrow a_1-b_1=198$ (2) $a_{100}+b_{100}-a_{101}-b_{101}=\dfrac{a_{100}}{a_1+1}-\dfrac{b_{100}}{b_1+199}=a_{100}\left(\dfrac1{a_1+1}-\dfrac{b_1+198}{(b_1+197)(b_1+199)}\right)$ We will prove $a_1+1<\dfrac{(b_1+197)(b_1+199)}{b_1+198}:=t$ which means $a_{100}+b_{100}>a_{101}+b_{101}$. But this is because \begin{align*} \left(\dfrac{a_1}{a_1+1}\right)^{100}(a_1+1)=a_{100}=b_{99}&=\dfrac{b_1+196}{b_1+195}\cdot\dfrac{b_1+194}{b_1+193}\cdot\cdots\cdot\dfrac{b_1+2}{b_1+1}\cdot b_1\\&=\dfrac{(b_1+197)(b_1+199)}{b_1+198}\cdot\boxed{\dfrac{b_1+198}{b_1+199}\cdot\dfrac{b_1+196}{b_1+197}}\cdot\dfrac{b_1+194}{b_1+195}\cdot\cdots\cdot\dfrac{b_1+2}{b_1+3}\cdot\dfrac{b_1}{b_1+1}\\&<t\cdot\boxed{\left(\dfrac{t-1}{t}\right)^2}\cdot \left(\dfrac{t-1}{t}\right)^{98}\\&=\left(\dfrac{t-1}{t}\right)^{100}t.
The answer to (1) should be 199 though
29.12.2022 10:28
Part 1: The value of $a_1 - b_1$ is 199. Note that the sequences can be rewritten as $(1+\sum^n_{i=1}\frac{1}{a_i})(a_{n+1}-a_n)=-1$ and $(1+\sum^n_{i=1}\frac{1}{b_i})(b_{n+1}-b_n)=1$ respectively. Summing up, we have $\sum^{100}_{n=1}[(1+\sum^n_{i=1}\frac{1}{a_i})(a_{n+1}-a_n)]=-100$, which can be simplified into $a_{101}(1+\sum^{100}_{i=1}\frac{1}{a_i})-a_1=0$ after expansion. Similarly, we would obtain $b_{101}(1+\sum^{100}_{i=1}\frac{1}{b_i})-b_1=200$. It follows after subtraction that $b_{101}(1+\sum^{100}_{i=1}\frac{1}{b_i})+a_{101}(1+\sum^{100}_{i=1}\frac{1}{a_i})+a_1-b_1=200$, which is equivalent to $\frac{b_{101}}{b_{101}-b_{100}}+\frac{a_{101}}{a_{101}-a_{100}}+a_1-b_1=200$, and $\frac{a_{101}b_{101}-a_{100}b_{101}+a_{101}b_{101}-a_{101}b_{100}}{a_{101}b_{101}-a_{100}b_{101}+a_{100}b_{100}-a_{101}b_{100}}+a_1-b_1=200$, which gives $a_1-b_1=199$ since $a_{100}b_{100}=a_{101}b_{101}$. Part 2: $a_{100}+b_{100}$ is larger. It is easy to see that $(a_n)$ is a strictly decreasing sequence and $(b_n)$ is a strictly increasing sequence. The following inequalities must thus hold: $$a_1>a_2>...>a_{99}>a_{100}=b_{99}>b_{98}>...>b_1>0$$. Claim: $\frac{1}{a_{99}}<\frac{1}{b_{100}}$. Proof: Note that $b_{100} = b_{99} + \frac{1}{1+\sum_{i=1}^{99}\frac{1}{b_i}}$ and $b_{99} = a_{100} = a_{99} + \frac{1}{1+\sum_{i=1}^{99}\frac{1}{a_i}}$ implies $$b_{100}=a_{99}+\frac{1}{1+\sum_{i=1}^{99}\frac{1}{b_i}}-\frac{1}{1+\sum_{i=1}^{99}\frac{1}{a_i}}$$. Clearly, $\frac{1}{1+\sum_{i=1}^{99}\frac{1}{b_i}}-\frac{1}{1+\sum_{i=1}^{99}\frac{1}{a_i}}<0$ because $1+\sum_{i=1}^{99}\frac{1}{b_i}>1+\sum_{i=1}^{99}\frac{1}{a_i}$. This completes the proof of the claim since $a_{99}>b_{100}$. Note that we have $a_{101}+b_{101}=a_{100}+b_{100}-\frac{1}{1+\sum_{i=1}^{100}\frac{1}{a_i}}+\frac{1}{1+\sum_{i=1}^{100}\frac{1}{b_i}}$. Moreover, the following inequality holds: $$1+\sum_{i=1}^{100}\frac{1}{a_i}=1+\sum_{i=1}^{98}\frac{1}{a_i}+\frac{1}{a_{99}}+\frac{1}{a_{100}}<1+\sum_{i=1}^{98}\frac{1}{b_i}+\frac{1}{b_{100}}+\frac{1}{b_{99}}=1+\sum_{i=1}^{100}\frac{1}{b_i}$$. This suffices to conclude that we indeed have $a_{100}+b_{100}>a_{101}+b_{101}$.
30.12.2022 22:31
Note: in this solution, empty products of the form $\prod_{j=0}^{-1} (blah) = 1$ Claim: $a_k = \frac{a_1^k}{(1+a_1)^{k-1}}$ for all $k\in \mathbb{N}$ Proof: Let $A(k)$ denote this assertion, and let $B(k)$ denote the assertion that $1+\sum\limits_{j=1}^k \frac{1}{a_j} = \frac{(1+a_1)^k}{a_1^k}$ The base case, $k=1$ has $A(1),B(1)$ clear. Inductive step: assume $k\ge 2$. $A(k-1),B(k-1) \to A(k)$: we have $$a_k = a_{k-1} - \frac{1}{1+\sum\limits_{j=1}^{k-1} \frac{1}{a_j}} = \frac{a_1^k}{(1+a_1)^{k-1}} - \frac{1}{\frac{(1+a_1)^{k-1}}{a_1^{k-1}}} = \frac{a_1^{k-1}}{(1+a_1)^{k-2}} - \frac{a_1^{k-1}}{(1+a_1)^{k-1}} = \frac{a_1^{k-1} (1+a_1-1)}{(1+a_1)^{k-1}} = \frac{a_1^k}{(1+a_1)^{k-1}}$$ $A(k),B(k-1) \to B(k) \colon 1+\sum\limits_{j=1}^k \frac{1}{a_j} = 1+\sum\limits_{j=1}^{k-1} \frac{1}{a_j} + \frac{1}{a_k} = \frac{(1+a_1)^{k-1}}{a_1^{k-1}} + \frac{(1+a_1)^{k-1}}{a_1^k} = \frac{(1+a_1)^k}{a_1^k}$ Claim: $$b_k = \frac{\prod\limits_{j=0}^{k-1} (b_1+2j)}{\prod\limits_{j=0}^{k-2} (b_1+1+2j)}$$ Let $C(k)$ denote this assertion, and let $D(k)$ denote the assertion that $1+\sum\limits_{j=1}^k \frac{1}{b_j} = \frac{\prod\limits_{j=0}^{k-1} (b_1+1+2j)}{\prod\limits_{j=0}^{k-1} (b_1+2j)}$. $C(1),D(1)$ clearly hold. $C(k-1), D(k-1)\to C(k)$: we have $$b_k = b_{k-1} + \frac{1}{\sum\limits_{j=1}^{k-1} \frac{1}{b_j}} = \frac{\prod\limits_{j=0}^{k-2} (b_1+2j)}{\prod\limits_{j=0}^{k-3} (b_1+1+2j)} + \frac{\prod\limits_{j=0}^{k-2} (b_1+2j)}{\prod\limits_{j=0}^{k-2} (b_1+1+2j)} = \frac{(1+b_1+1+2(k-2))\prod\limits_{j=0}^{k-2} (b_1+2j)}{\prod\limits_{j=0}^{k-2} (b_1+1+2j)} = \frac{\prod\limits_{j=0}^{k-1} (b_1+2j)}{\prod\limits_{j=0}^{k-2} (b_1+1+2j)}$$ $C(k), D(k-1) \to D(k)$: we have $$1+\sum\limits_{j=1}^k \frac{1}{b_j} = 1+\sum\limits_{j=1}^{k-1} \frac{1}{b_j} + \frac{1}{b_k} = \frac{\prod\limits_{j=0}^{k-2} (b_1+1+2j)}{\prod\limits_{j=0}^{k-2} (b_1+2j)} + \frac{\prod\limits_{j=0}^{k-2} (b_1+1+2j)}{\prod\limits_{j=0}^{k-1} (b_1+2j)} = \frac{(1+b_1+2(k-1))\prod\limits_{j=0}^{k-2} (b_1+1+2j)}{\prod\limits_{j=0}^{k-1} (b_1+2j)} = \frac{\prod\limits_{j=0}^{k-1} (b_1+1+2j)}{\prod\limits_{j=0}^{k-1} (b_1+2j)}$$ 1) It follows that $$1+a_1^{-1}=\frac{1+a_1}{a_1} = \frac{a_{100}}{a_{101}} = \frac{b_{101}}{b_{100}} = \frac{b_1+2(101-1)}{b_1+2(101-1)-1} = 1+(b_1+199)^{-1}$$ So $a_1-b_1=199$ 2) If $a_{100}=b_{99}$ then we see that $$a_{100}-a_{101} = \left( 1-\frac{1}{1+a_1}\right)^{100}$$ $$b_{101}-b_{100} = \prod\limits_{j=1}^{100} \left( 1-\frac{1}{2j-1+b_1} \right)$$ Lemma: $$\left( 1-\frac{1}{x-k}\right) \left( 1-\frac{1}{x+k}\right) < \left( 1-\frac{1}{x}\right)^2$$ Proof: Expand LHS to get this is equivalent to $\frac{(x-1)^2-k^2}{x^2-k^2} < \frac{(x-1)^2}{x^2}$ which is clear. Case 1: $a_1-b_1 \ge 99$. Then $$b_{101}-b_{100} < \left(1-\frac{1}{100+b_1}\right)^{100} \le \left(1-\frac{1}{1+a_1}\right)^{100} $$ Case 2: $a_1-b_1 < 99$. It suffices to show that $\frac{1}{1+a_1} = \frac{a_{100}-a_{101}}{a_{100}} > \frac{b_{101}-b_{100}}{b_{99}} = \frac{(b_1+198)}{(b_1+197)(b_1+199)}$ Note $\frac{1}{1+a_1} > \frac{1}{100+b_1} > \frac{1}{b_1+197} > \frac{(b_1+198)}{(b_1+197)(b_1+199)}$ Since $a_{100}-a_{101} > b_{101}-b_{100}, a_{100}+b_{100} > a_{101}+b_{101}$
01.01.2023 21:01
02.01.2023 13:25
bora_olmez wrote: Part 2 is slightly underwhelming because rather than comparing $a_1$ and $b_1+197-\frac{1}{b_1+198}$ it is sufficient to simply compare $a_1$ and $b_1+196$. Fortunately (but unfortunately for your solution), this is not the case and hence the problem is not underwhelming at all. Indeed, it would be enough to prove that $a_1<b_1+196$ but this is simply not true, indeed it is quite easy to prove that for large $a_1$ and $b_1$ satisfying the condition we have $a_1-b_1 \to 197$. The mistake in your proof is when you multiply the inequalities to get \[\left( \frac{b_1+196}{b_1+197} \right)^{99} > \frac{\prod_{i=0}^{97} (b_1+2i)}{\prod_{i=0}^{97} (b_1+2_i+1)} \]but you actually only multiply $98$ inequalities so that the LHS should have $98$ instead of $99$.
20.01.2023 16:22
Did a video solution here: https://youtu.be/hRB5hQWtUfI
25.01.2023 18:37
Here is a non-inductive solution if anyone is interested (sorry not familiar with LaTeX).
Attachments:
CMO_11zon.pdf (520kb)