• Support PF! Buy your school textbooks, materials and every day products Here!

I think of it as hard proof by induction

  • #1
rock.freak667
Homework Helper
6,230
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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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
rock.freak667
Homework Helper
6,230
31
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
Dick
Science Advisor
Homework Helper
26,258
618
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
exk
119
0
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
rock.freak667
Homework Helper
6,230
31
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
Vid
401
0
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
Vid
401
0
I see no problems with your proof.
 
  • #9
rock.freak667
Homework Helper
6,230
31
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

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
Vid
401
0
(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.
 

Related Threads for: I think of it as hard proof by induction

  • Last Post
Replies
6
Views
723
Replies
6
Views
1K
  • Last Post
Replies
16
Views
18K
  • Last Post
Replies
2
Views
881
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
591
Top