Advanced Math Problem of the Week 10/17/2017

[PF PotW Robot]

Here is this week's advanced math problem. We have several members who will check solutions, but we also welcome the community in general to step in. We also encourage finding different methods to the solution. If one has been found, see if there is another way. Using spoiler tags is optional. Occasionally there will be prizes for extraordinary or clever methods. Spoiler tags are optional.Consider the sequence $\{a_k\}_{k\ge 1}$ is defined by $a_1=1$, $a_2=\dfrac{1}{2}$ and $a_{k+2}=a_k+\dfrac{a_{k+1}}{2}+\dfrac{1}{4a_ka_{k+1}}$ for $k\ge 1.$

Prove that $\dfrac{1}{a_1a_3}+\dfrac{1}{a_2a_4}+\dfrac{1}{a_3a_5}+\cdots+\dfrac{1}{a_{98}a_{100}}<4$.

(PotW thanks to our friends at http://www.mathhelpboards.com/)

 

[StoneTemplePython]

Here is my proof. It's a bit longer and uglier than what I wanted. I assumed direct calculation of a few numbers (albeit not running a for loop over the entire series) was allowed. I suspect there is a much shorter approach.

FWIW, it seemed to me that a better posed problem would be to prove:

$\sum_{k=1}^{n} \frac{1}{a_k a_{k+2}} \lt 4$ for arbitrary natural number n, or perhaps just prove $\sum_{k=1}^{\infty} \frac{1}{a_k a_{k+2}} \lt 4$
- - - -
The inspiration for this post is:

$\sum_{k=2}^n \big(\frac{1}{k}\big)^2 \lt \sum_{k=2}^n \frac{1}{k(k-1)} = 1 - \frac{1}{n} \leq 1$

for natural numbers where $2\leq k \lt n$
additionally, the fact that all numbers in our series are strictly positive allows us to make use of things like $GM \leq AM$

- - - -
It is sometimes useful to calculate a few values out first. Values from $a_3, a_4, a_5, a_6$ and $a_7$ are shown directly in the end piece of this post.

Our goal is to prove

$\sum_{k=1}^{98} \frac{1}{a_k a_{k+2}} = \big(\sum_{k=1}^{4} \frac{1}{a_k a_{k+2}}\big) + \sum_{k=5}^{98} \frac{1}{a_k a_{k+2}} \lt 4$

via above mentioned calculations, we have:

$\big(\sum_{k=1}^{4} \frac{1}{a_k a_{k+2}}\big)= \frac{1}{a_1 a_{3}} + \frac{1}{a_2 a_{4}} + \frac{1}{a_3 a_{5}} + \frac{1}{a_4 a_{6}} \approx 2.187 \lt 2.2$

The proof is in some sense only 3 lines, with some justification provided at the end

- - - -
first:

$\sum_{k=1}^{98} \frac{1}{a_k a_{k+2}} \lt 2.2 + \sum_{k=5}^{98} \frac{1}{a_k a_{k+2}} \lt 2.2 + \frac{1}{2}\Big(\big(\sum_{k=5}^{98} \frac{1}{a_k^2} \big) + \big(\sum_{k=5}^{98} \frac{1}{ a_{k+2}^2}\big)\Big) \lt 2.2 + \frac{1}{2}\Big(2\big(\sum_{k=5}^{100} \frac{1}{a_{k}^2} \big)\Big) = 2.2 + \Big(\sum_{k=5}^{100} \big(\frac{1}{a_{k}}\big)^2\Big)$

by application of Cauchy Schwarz in additive form (or equivalently: $GM \leq AM$).

- - - -
second:

if we set: $r:= k-3$ we can re-write the RHS as

$2.2 + \Big(\sum_{k=5}^{100} \big(\frac{1}{a_{k}}\big)^2\Big) = 2.2 + \Big(\sum_{r=2}^{97} \big(\frac{1}{a_{r+3}}\big)^2\Big)$

- - - -
finally:

$\sum_{k=1}^{98} \frac{1}{a_k a_{k+2}} \lt 2.2 + \Big(\sum_{r=2}^{97} \big(\frac{1}{a_{r+3}}\big)^2\Big) \leq 2.2+ \Big(\sum_{r=2}^{97} \frac{1}{r(r-1)}\Big) \leq 2.2 + \big(1\big) = 3.2 \lt 4$

which completes the proof.
- - - -
note: this readily generalizes to an infinite series where:

$\sum_{k=1}^{\infty} \frac{1}{a_k a_{k+2}} \lt 2.2 + \Big(\sum_{k=2}^{\infty} \frac{1}{k(k-1)}\Big) = 3.2 \lt 4$
- - - - - - - - - - - - - - - - - - - - - - - -
supporting info:
proof that $\sum_{r=2}^{n}\big(\frac{1}{a_{r+3}}\big)^2 \leq \sum_{r=2}^{n}\frac{1}{r(r-1)}$

for any natural number $n \geq 2$
- - - -
we want to show

$r(r-1) \leq a_{r+3}^2$
because this means

$\frac{1}{r(r-1)} \geq \frac{1}{a_{r+3}^2}$

noting that all values are positive for both $(r-1)$ and $a_{r+3}$.

We can equivalently seek to prove:

$\big(r(r-1)\big)^\frac{1}{2} \leq a_{r+3}$

$\big(r(r-1)\big)^\frac{1}{2} \leq \frac{1}{2}\big(r + (r-1)\big) = r - 0.5 \leq a_{r+3}$
by $GM \leq AM$
- - - -

Hence all we really need to prove is: $a_{r+3} \geq r - 0.5$
by direct calculation, we verify this holds in the case of $a_5$ through $a_7$ as shown below.

$\begin{bmatrix} & & a_3 & = 1.75 & \\ & & a_4 & \approx 1.6607 & \\ r = 2 & \to & a_5 & \approx 2.6663 &\gt 1.5 \\ r = 3 & \to & a_6 & \approx 3.0503 &\gt 2.5 \\ r = 4 & \to & a_7 & \approx 4.222 &\gt 3.5 \end{bmatrix}$

From here we may use induction: assume true for some $r$ now we need to prove it must be true for $r+1$, i.e. prove

$a_{r + 4} = a_{r + 3+1} \geq (r+1) -0.5 = r+0.5$

using our recurrence, noting that $\frac{1}{4 a_{r+3}a_{r+2} } \gt 0$, and then using our strong inductive hypothesis, we have

$a_{r+4} = \frac{1}{2}a_{r+3} + a_{r+2} +\frac{1}{4 a_{r+3}a_{r+2} } \gt \frac{1}{2}a_{r+3} + a_{r+2} \geq \frac{1}{2}\big(r - 0.5\big) + \big((r - 1) -0.5\big) = 1.5r - 1.75$

Hence we are interested in:

$1.5r - 1.75 \geq r + 0.5$
$0.5r \geq 2.25$
$r \geq 4.5$

Therefore the relationship must hold true for natural numbers $r \geq 5$ and we verified it holds via direct calculation for smaller values of $r$. Thus we've proven for any natural number $r\geq 2$

$\big(\frac{1}{a_{r+3}}\big)^2 \leq \frac{1}{r(r-1)}$

hence

$\sum_{r=2}^{n}\big(\frac{1}{a_{r+3}}\big)^2 \leq \sum_{r=2}^{n}\frac{1}{r(r-1)} \leq 1$