
Algebra PreAlgebra and Basic Algebra Math Forum 
 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$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^{n1}$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*}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^{n1}\qquad(1)$or not. Trying to solve the lefthand side for $\displaystyle n$, we get $\displaystyle 4^n < 6 \cdot 4^{n1} + 1$and, since logarithms are monotonic, (and $\displaystyle \ln 4$ is positive), $\displaystyle n < \frac {\ln(6 \cdot 4^{n1} + 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 selfevident $\displaystyle 6 \cdot 4^{n1} < 6 \cdot 4^{n1} + 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^{n1})} {\ln 4} < \frac {\ln(6 \cdot 4^{n1} + 1)} {\ln 4} \qquad (3)$The LHS is my middle man, which I can further manipulate into $\displaystyle \frac {\ln(6 \cdot 4^{n1})} {\ln 4} = \frac {\ln 6 + (n1)\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? 
December 15th, 2018, 11:08 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,757 Thanks: 2138 
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. 
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. 
December 16th, 2018, 05:53 AM  #4 
Senior Member Joined: Sep 2016 From: USA Posts: 627 Thanks: 398 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}.\] 
December 16th, 2018, 11:14 AM  #5 
Global Moderator Joined: Dec 2006 Posts: 20,757 Thanks: 2138 
As the $x_1 = 7/4$ example shows, the x$ sequence may "catch up" despite starting at a lower value.


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 