My Math Forum Please fix my intuition

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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?
 December 15th, 2018, 11:08 PM #2 Global Moderator   Joined: Dec 2006 Posts: 20,370 Thanks: 2007 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
 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: 578 Thanks: 345 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
 December 16th, 2018, 11:14 AM #5 Global Moderator   Joined: Dec 2006 Posts: 20,370 Thanks: 2007 As the $x_1 = 7/4$ example shows, the x\$ sequence may "catch up" despite starting at a lower value.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post triplekite Differential Equations 3 June 11th, 2013 04:22 PM taylor_1989_2012 Algebra 1 March 14th, 2013 08:26 AM Sefrez Calculus 1 August 16th, 2011 03:17 PM Sefrez Calculus 1 February 24th, 2011 02:58 AM Billiam411 Calculus 4 October 27th, 2007 07:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top