My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree2Thanks
  • 1 Post By skipjack
  • 1 Post By SDK
Reply
 
LinkBack Thread Tools Display Modes
December 15th, 2018, 08:50 PM   #1
Newbie
 
Joined: Dec 2018
From: Germany

Posts: 5
Thanks: 0

Please fix my intuition

Hi, folks,
apologies for the mammoth post, but I hope this is at least fun.

Here is my problem. I have two recurrence sequences, $\displaystyle x_n$ and $\displaystyle y_n$, where the first "grows faster" than the second (or so I thought). Afterwards, I proved that $\displaystyle x_n < y_n$, always... which leaves my first intuition (that the first grew faster) in tatters.

These are the players:
$\displaystyle x_1 = 1$ ; $\displaystyle x_{n+1} = 4x_n + 1$
$\displaystyle y_1 = 2$ ; $\displaystyle y_{n+1} = 4y_n$
At the beginning, $\displaystyle x_1 < y_1$ (1 < 2), and I would have thought that $\displaystyle x_n$, growing faster, would eventually overcome $\displaystyle y_n$. It turns out that I am provably wrong, but... what is wrong with this first intuition? (If you can tell me without even looking at the proof that follows, please feel free...)

To prove the above, I will use the closed form of the two sequences. Clearly
$\displaystyle y_n = 2 \cdot 4^{n-1}$
and it can be proved by induction than
$\displaystyle x_n = \frac{4^n - 1} 3$
For this induction proof, the initial step ($\displaystyle x_1=1$) is obvious; and for the induction step, we start assuming it true for $\displaystyle n=k$, and use the recurrence rule to compute
$\displaystyle \begin{align*}
x_{k+1} &= 4 \left( \frac{4^k - 1} 3 \right) + 1 \\
&= \frac{4^{k+1} - 4} 3 + 1 \\
&= \frac{4^{k+1} - 1} 3
\end{align*}$
So, now that I have the two closed forms, what I wish to prove is whether
$\displaystyle \frac{4^n - 1} 3 < 2 \cdot 4^{n-1}\qquad(1)$
or not. Trying to solve the left-hand side for $\displaystyle n$, we get
$\displaystyle 4^n < 6 \cdot 4^{n-1} + 1$
and, since logarithms are monotonic, (and $\displaystyle \ln 4$ is positive),
$\displaystyle n < \frac {\ln(6 \cdot 4^{n-1} + 1)} {\ln 4} \qquad (2)$
I'd hope to convince you that proving (2) is the same as proving (1).

To prove (2), I will find something in the middle, and prove that it is smaller than the RHS but larger that the LHS. That middle "something" is going to be the RHS without that pesky "+ 1" that prevents further manipulation. I'll begin from the self-evident
$\displaystyle 6 \cdot 4^{n-1} < 6 \cdot 4^{n-1} + 1$
(because the LHS is just the RHS plus one); and then take logs (which are monotonic) and divide by a positive quantity, to obtain
$\displaystyle \frac {\ln(6 \cdot 4^{n-1})} {\ln 4} < \frac {\ln(6 \cdot 4^{n-1} + 1)} {\ln 4} \qquad (3)$
The LHS is my middle man, which I can further manipulate into
$\displaystyle \frac {\ln(6 \cdot 4^{n-1})} {\ln 4} = \frac {\ln 6 + (n-1)\ln 4} {\ln 4} = n + \frac{\ln 6}{\ln 4} - 1 > n \qquad (4)$
since clearly $\displaystyle \ln 6 > \ln 4$ and the extra summands after $\displaystyle n$ add to something positive. So we're done: (3) and (4) prove (2), which proves (1).

So, having convinced you that the first sequence never overcome the second... what was wrong with believing that, if the first "grows faster", it should have overcome the second?
dodo is offline  
 
December 15th, 2018, 11:08 PM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 20,971
Thanks: 2222

Use induction: $y_k \geqslant x_k + 1 \implies 4y_k \geqslant 4x_k + 4 > 4x_k + 1 \implies y_{k+1} > x_{k+1}$.

To "break even", use $x_1 = 5/3,\ y_1 = 2$, then $x_n + 1/3 = y_n$ is similarly provable by induction.
Thanks from dodo
skipjack is online now  
December 16th, 2018, 02:56 AM   #3
Newbie
 
Joined: Dec 2018
From: Germany

Posts: 5
Thanks: 0

Ah, thanks. And with say, $\displaystyle x_1 = 7/4$, one series catches the other at $\displaystyle x_2=y_2$, and then $\displaystyle x_n > y_n$ for n > 2.

I guess the moral of the story is not to draw conclusions from the recurrence rule alone; the initial value makes a difference when finding the closed form. Comparing the recurrence rules and comparing the derivatives of the closed forms are two very different animals.

Thanks again.
dodo is offline  
December 16th, 2018, 05:53 AM   #4
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 645
Thanks: 408

Math Focus: Dynamical systems, analytic function theory, numerics
Your intuition is correct, the sequence with the faster growth rate should dominate. However, the "growth" in this case should roughly measure how large the next term in each sequence is compared to the present term. For both sequences, this is a function of the current term in the sequence and the $x$ sequence has a smaller initial value. That is why it has a slower growth. The recursion formula doesn't tell the whole story about the growth rate, the initial value matters.

I think the easy intuitive device here is to consider the analogous initial value problems: $\dot{x} = 4x + 1, x(0) = 1$ and $\dot{y} = 4y, y(0) = 2$. As with any IVP, the solution is a function not only of the derivative, but of the initial data. The claim that $x$ grows slower than $y$ is the same as saying that the trajectory for the first IVP is bounded by the second. This is easy to see since the solutions to each IVP are:
\[y(t) = 2e^{4t} \qquad x(t) = 2e^{4t} - \frac{1}{4} - \frac{3}{4}e^{4t}.\]
Thanks from dodo
SDK is offline  
December 16th, 2018, 11:14 AM   #5
Global Moderator
 
Joined: Dec 2006

Posts: 20,971
Thanks: 2222

As the $x_1 = 7/4$ example shows, the x$ sequence may "catch up" despite starting at a lower value.
skipjack is online now  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
fix, intuition, recurrence sequences



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Intuition behind differential element dA? triplekite Differential Equations 3 June 11th, 2013 04:22 PM
Vector Intuition check taylor_1989_2012 Algebra 1 March 14th, 2013 08:26 AM
A better intuition? Sefrez Calculus 1 August 16th, 2011 03:17 PM
Very simple, just need some intuition. Sefrez Calculus 1 February 24th, 2011 02:58 AM
Intuition Question (multivariable) Billiam411 Calculus 4 October 27th, 2007 07:39 PM





Copyright © 2019 My Math Forum. All rights reserved.