Waste less time on Facebook — follow Brilliant.


The question is quite famous and is generally included under the topic of induction, but I didn't actually catch how to do it. And it goes as follows:

Two sequences \((a_{1},a_{2},...)\) and \((b_{1},b_{2},...)\) are defined as \(a_{1}=3, a_{n}=3^{a_{n-1}}\) and \(b_{1}=4, b_{n}=4^{b_{n-1}}\). Show that \(a_{1000}>b_{999}\).

Thank you to everyone who shall participate in the discussion and help me. Please explain how to do it, as well.

Note by Shourya Pandey
4 years, 1 month ago

No vote yet
9 votes


Sort by:

Top Newest
Comment deleted Jun 01, 2013

Log in to reply

@Sebastian Puerto The solution as you presented is not true at all.

Apart from Bob's statement the you are assuming X to prove X, your inequalities are not valid at all.

When you say, "we must prove that \( 3^{a_{n+1}} > 3^a_n * 4^b_n \)" (ie \( A_{n+2} > a_{n+1} b_{n+1} \), you cannot assume that the stamens is true.

Moreover, if you follow your logic, you show that statement implies that \( a_{n+1} > b_{n+1} \), which is true by the induction hypothesis. You have not used the induction hypothesis to prove what you want.

There are some good ideas that you used, but you should review implications of inequalities and presentation of induction, to ensure that what you are thinking is exactly what you are communicating. Calvin Lin Staff · 4 years, 1 month ago

Log in to reply

@Calvin Lin Thanks, I really felt something was wrong with my "proof", but I didn't understan what was it. I half studied induction just to participate in this discussion, but it seems that I lacked more understanding about the topic. Sebastian Puerto · 4 years, 1 month ago

Log in to reply

@Sebastian Puerto I don't follow. It seems like you are assuming what you are trying to prove, and then showing that it is true, which does not satisfy the induction criteria. Bob Krueger · 4 years, 1 month ago

Log in to reply

First, you should prove that \(a_{n}>b_{n-1}\) using induction. For the base case, let \(n=2\), and it is obvious that \(a_{n}=a_2=3^{a_1}=3^3=27\) is greater than \(b_{n-1}=b_1=4\).

Now we must show that \(a_{n+1}>b_n\) if we assume that \(a_n>b_{n-1}\). \(a_{n+1}=3^{a_n}\) and \(b_n=4^{b_{n-1}}.



\(a_n \cdot \log_4{3} > b_{n-1}\)


This is the best I could do. I'm not sure how to proceed from here. Ricky Escobar · 4 years, 1 month ago

Log in to reply

@Ricky Escobar That's is a good start. However, as you realized, you needed to use a statement that is stronger than the induction hypothesis that you currently have. That factor of \( \log_4 3 \) seems to mess things up.

This suggests that you should make your induction hypothesis stronger, which was what Sebastian was doing.

For example, if the induction hypothesis was that \( a_{n+1} > 2 b_n \), then you can see that the previous statement we wanted is true. However, of course, this strengthen the inequality that we get in the induction step, and hence may longer be true. Thus part of this problem is to find the stronger induction statement to prove.

I call this method of induction proof "stronger induction" (this terminology is not standard), because you have to guess at a stronger statement to show than the obvious guess. I am planning a series of posts on induction, and hope to cover this at some point in the future. Calvin Lin Staff · 4 years, 1 month ago

Log in to reply

@Calvin Lin Well so the "stronger induction" here refers to the "stronger inequality" which is being used to prove the statement true. Shourya Pandey · 4 years, 1 month ago

Log in to reply

@Shourya Pandey The word stronger refers to proving a stronger statement, then that given by the (initial) induction hypothesis. In this particular case, it is a stronger inequality.

Another example of a question approached by "stronger induction" is as follows:

\(a, b\) are positive integers such that \( \frac {2ab}{a^2+b^2} = \sin \theta\), show that \( (a^2+b^2)^n \sin n\theta\) is an integer.

For this example, the induction hypothesis of

Let \(P_n\) be the proposition that \( (a^2+b^2)^n \sin n\theta\) is an integer.

is not sufficient enough for us to work on the induction step. Calvin Lin Staff · 4 years, 1 month ago

Log in to reply

@Ricky Escobar I had proceeded in a similar manner, but to no avail. Maybe we need to prove it for certain powers or pattern and complete the proof by reverse induction, because I am sure that reverse induction works. But a reference point is what is required to be found. Shourya Pandey · 4 years, 1 month ago

Log in to reply

Comment deleted May 30, 2013

Log in to reply

@Superman Son This is a false statement. It only holds for k<5 Bob Krueger · 4 years, 1 month ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...