I think of it as hard proof by induction

In summary: Ok, so the statement is true for n=N+1. But it's also true for n=N. So it's true for all n.I see no problems with your proof.In summary, the statement is true for all n.
  • #1

rock.freak667

Homework Helper
6,223
31
[SOLVED] I think of it as hard proof by induction

Homework Statement



given for the sequence [itex]a_1,a_2,a_3,a_4,...[/itex],[itex]a_1=1[/itex] and that

[tex]a_{n+1}=(a_n+\frac{1}{a_n})^{\lambda}[/tex]

where[itex]\lambda>1[/itex].Prove by mathematical induction that,for [itex]n \geq 2[/itex]

[tex]a_n \geq 2^{g(n)}[/tex]

where [itex]g(n)=\lambda^{n-1}[/itex]

Prove also,for [itex]n \geq 2[/itex]

[tex]\frac{a_{n+1}}{a_n}>2^{(\lambda -1)g(n)}[/tex]

Homework Equations





The Attempt at a Solution



well what I tried to do was to consider [itex]a_{n+1}-2^{g(n)}[/itex]

which after simplification gives:

[tex] \frac{(a_n^2+1)^{\lambda}}{a_n^{\lambda}}-2^{g(n)}[/itex]

which I then said should be greater than or equal to zero since the fraction on the left is +ve and 2^g(n) is positive since lambda is >1. Is this a good way to start?
 
Physics news on Phys.org
  • #2
Not really. I think you are supposed to use induction. Prove the statement is true for n=1. Then prove is the statement is true for n, then it's true for n+1. Isn't that how induction is supposed to go? What you've done so far doesn't look very 'inductive'.
 
  • #3
Dick said:
Not really. I think you are supposed to use induction. Prove the statement is true for n=1. Then prove is the statement is true for n, then it's true for n+1. Isn't that how induction is supposed to go? What you've done so far doesn't look very 'inductive'.

Well what I was essentially trying to do was to find an expression for a_n+1-2^g(n) and then add,subtract,multiply and divide various things to [itex]a_n \geq 2^{g(n)}[/itex] and then eventually say that from my expression a_n+1 >= 2^g(n)
 
  • #4
Yeah, I know. But the problem says 'use induction'. And that might be the best way to go. I'll warn you, I haven't actually tried to do it.
 
  • #5
As Dick mentioned induction may be the way to go:

[tex]a_2=2^{\lambda}[/tex]

Take your expression now and show that the statement is true for n=2 (I guess this is also your inductive hypothesis):

[tex]
\frac{(a_n^2+1)^{\lambda}}{a_n^{\lambda}}-2^{g(n)} \geq 0 --> \frac{(a_n^2+1)}{a_n} \geq 2^{\lambda^{n-2}}
[/tex]

So then:
[tex]\frac{(a_2^2+1)}{a_2} \geq 2 --> \frac{(2^{2\lambda}+1)}{2^{\lambda}} \geq 2 [/tex]

So now you need to find a way to express the relation for n=k+1. I guess expanding a couple of terms may be helpful, but I always came back to the general form that you proposed.
 
  • #6
Then just say:

Assume true for n=N

[itex]a_N \geq 2^{g(n)}[/itex]

+ [itex]\frac{1}{a_N}[/itex]

[tex]a_N +\frac{1}{a_N} \geq 2^{g(n)} +\frac{1}{a_N}[/tex]


Raise both sides to the power of [itex]\lambda[/itex]


[tex](a_N +\frac{1}{a_N})^{\lambda} \geq (2^{g(n)} +\frac{1}{a_N})^{\lambda}[/tex]

and then say that

[tex](2^{g(n)} +\frac{1}{a_N})^{\lambda} \geq 2^{g(N+1)}[/tex]

and so

[tex]a_{N+1}>2^{g(N+1)}[/tex]

and hence true by PMI ?
 
  • #7
We need to show that

(an + 1/an)^t >= 2^(t^(n))
Observation:
t*ln(an + 1/an) >=t^(n)ln(2)
ln(an + 1/an) >= t^(n-1)(ln(2))
an + 1/an >= 2^(t^(n-1))
Since t >= 1, it's an increasing sequence. Thus,
an + 1/an > an >= 2^(t^(n-1)) by the inductive hypothesis. QED.
 
  • #8
I see no problems with your proof.
 
  • #9
Vid said:
We need to show that

(an + 1/an)^t >= 2^(t^(n))
Observation:
t*ln(an + 1/an) >=t^(n)ln(2)
ln(an + 1/an) >= t^(n-1)(ln(2))
an + 1/an >= 2^(t^(n-1))
Since t >= 1, it's an increasing sequence. Thus,
an + 1/an > an >= 2^(t^(n-1)) by the inductive hypothesis. QED.

hm.didn't think about taking ln...interesting

Vid said:
I see no problems with your proof.

But I might need to justify why

[tex](2^{g(n)} +\frac{1}{a_N})^{\lambda} \geq 2^{g(N+1)}[/tex]

so I would just say that the 2^g(n)+(anything) must be bigger than 2^(g(n+1)) since a_n is greater than zero
 
  • #10
(2^(t^(n-1) + 1/an)^t >= 2^(t^(n-1)*t) = 2^(t^n) = 2^(g(n+1)). The inequality holds since t> 1 and an is postive.
 

What is hard proof by induction?

Hard proof by induction is a type of mathematical proof used to show that a statement or property holds for all natural numbers. It involves using a base case to prove that the statement holds for the first natural number, and then using the induction hypothesis to prove that the statement holds for the next natural number, and so on.

How is hard proof by induction different from regular induction?

Hard proof by induction is a more rigorous and formal version of induction. It requires a base case and an induction hypothesis, whereas regular induction may only involve a general pattern or observation. Hard proof by induction is used to prove statements about all natural numbers, while regular induction can be used for any set of objects or numbers.

Why is hard proof by induction important in science?

Hard proof by induction is important in science because it allows us to prove that a certain property or statement holds for all natural numbers, which can be applied to various scientific theories and experiments. It is also a fundamental tool in the development and understanding of mathematical concepts and theories.

What are the common mistakes made when using hard proof by induction?

Some common mistakes made when using hard proof by induction include using the wrong base case, assuming the statement holds for all natural numbers without proving it, and making incorrect assumptions about the induction hypothesis. It is important to carefully follow the steps of hard proof by induction to avoid these mistakes.

Can hard proof by induction be used for any type of statement?

No, hard proof by induction can only be used for statements that hold for all natural numbers. It cannot be used for statements that involve real numbers or other types of objects. Additionally, the statement must follow a certain pattern or rule that can be generalized for all natural numbers.

Suggested for: I think of it as hard proof by induction

Replies
6
Views
696
Replies
15
Views
884
Replies
4
Views
718
Replies
6
Views
934
Replies
7
Views
894
Replies
4
Views
945
Replies
3
Views
465
Back
Top