Haggling problem

Question

Adam is trying to sell Bob a bike for $a$ dollars.

Bob does not agree on the price $b$ ($0 < b < a$).

Adam does not agree on this price but does lower his initial price to $\dfrac{a+b}{2}$ dollars.

Bob responds by offering $\dfrac{b+\frac{a+b}{2}}{2}$ dollars.

They continue haggling this way, each time taking the average of the previous two amounts.

On what price will they converge? Express this price in terms of the two initially proposed amounts $a$ and $b$.

---

Answer 1

1. We first write the series of bids: Start with $a$ and then $$ \tfrac{b}{1} \to \tfrac{a+b}{2} \to \tfrac{2b+(a+b)}{4}=\tfrac{a+3b}{4} \to \tfrac{2(a+b)+(a+3b)}{8}=\tfrac{3a+5b}{8} \to \tfrac{2(a+3b)+(3a+5b)}{16}=\tfrac{5a+11b}{16}\to\dotsb \tag{*} $$

2. The denominators in (*) are the series $\{ 2^0, 2^1, 2^2, 2^3, 2^4,\dotsc\}$.

3. The nominators in (*) are as follows: $$ 0a+1b \to 1a+1b \to 1a+3b \to 3a+5b \to 5a+11b \to 11a+21b \to \dotsb $$

4. Let us rewrite the coefficients of $a$ and $b$ as sequences: $$ \begin{align*} \text{coefficients of $a$}: \{a_n\mid n\geq0\}=\{ 0, 1, 1, 3, 5, 11, 21, 43, \dotsc \} \\ \text{coefficients of $b$}: \{b_n\mid n\geq0\}=\{ 1, 1, 3, 5, 11, 21, 43, 85, \dotsc \} \end{align*} $$

5. Two sequences are the same: $a_n=s_n$ and $b_n=s_{n+1}$ for $n\geq0$, where $$ s_0=0, \quad s_1=1, \quad s_n = 2s_{n-2} + s_{n-1} \quad\text{for $n\geq2$} $$ Note that $a_n+b_n=s_n+s_{n+1}=2^n$ for all $n\geq0$. Moreover, $$ s_n = 2s_{n-2} + s_{n-1} = 2(2^{n-2}-s_{n-1})+s_{n-1} = 2^{n-1}-s_{n-1} \quad\text{for $n\geq2$} $$ so that $$ \frac{1}{2}\left(\frac{s_{n-1}}{2^{n-1}}\right) + \frac{s_n}{2^n}=\frac{s_{n-1} + s_n}{2^n} = \frac{2^{n-1}}{2^n}=\frac{1}{2} \tag{**} $$

6. If the sequence $\dfrac{s_n}{2^n}$ converges to $p$, then the equation (**) follows that $\frac{1}{2}p+p=\frac{1}{2}$ so that $$ \lim_{n\to\infty} \frac{s_n}{2^n} = p = \frac{1}{3} \tag{***} $$

7. Let us rewrite the bids in (*) as an equation: $$ \frac{a_na+b_nb}{2^n} = \frac{s_na+s_{n+1}b}{2^n} = \frac{s_na+(2^n-s_n)b}{2^n} = \frac{s_n}{2^n}(a-b) + b \quad\text{for $n\geq0$} $$

On what price will they converge? Express this price in terms of the two initially proposed amounts a and b.

Now from the limit in (***), the final answer is: $$ \lim_{n\to\infty} \left[ \frac{s_n}{2^n}(a-b) + b \right] = \frac{1}{3}(a-b)+b $$

Answer 2

Let $a_n$ be the $n^{\rm th}$ bid of $A$, and let $b_n$ be the $n^{\rm th}$ bid of $B$, with $a_0=a$, $b_0=b<a$. Then $$a_n={1\over2}(a_{n-1}+b_{n-1}),\quad b_n={1\over2}(a_n+b_{n-1})={1\over4}a_{n-1}+{3\over4}b_{n-1}\qquad(n\geq1)\ .\tag{1}$$ It follows that $$[b_n,a_n]\subset[b_{n-1},a_{n-1}]\>,\quad a_n-b_n={1\over4}(a_{n-1}-b_{n-1})\qquad(n\geq1)\ .$$ This shows that $\lim_{n\to\infty} a_n=\lim_{n\to\infty}b_n=\alpha$ for a certain $\alpha\in[b,a]$. Furthermore it follows from $(1)$ that $$a_n+2b_n=a_{n-1}+2b_{n-1}\qquad (n\geq1)\ ,$$ so that $a_n+2b_n=a+2b$ for all $n\geq0$, and this implies $$\alpha={1\over3}\lim_{n\to\infty}(a_n+2b_n)={a+2b\over3}\ .$$