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

Inductive proof

  • Thread starter amarch
  • Start date
  • #1
7
0

Homework Statement



for reals x and y with x greater than y, prove that n*x^(n-1)(x-y)>=x^n-y^n for n>0.

Homework Equations





The Attempt at a Solution



Let p(n) be that the statement is true for some n.
base case: obviously follows

inductive step: assume p(k) is true for some k.
Look at (n+1)x^(n-1+1)(a-b) = (n*x^n+x^n)(x-y)
= n*x*x^n - n*y*x^n+x*x^n-y*x^n

I'm stuck here. I know there is a way to do it using the property (x^n-y^n) = (x-y)(some polynomial), but we were specifically asked not to use that and to do it by induction.
 

Answers and Replies

  • #2
392
17

Homework Statement



for reals x and y with x greater than y, prove that n*x^(n-1)(x-y)>=x^n-y^n for n>0.

Homework Equations





The Attempt at a Solution



Let p(n) be that the statement is true for some n.
base case: obviously follows

inductive step: assume p(k) is true for some k.
Look at (n+1)x^(n-1+1)(a-b) = (n*x^n+x^n)(x-y)
= n*x*x^n - n*y*x^n+x*x^n-y*x^n

I'm stuck here. I know there is a way to do it using the property (x^n-y^n) = (x-y)(some polynomial), but we were specifically asked not to use that and to do it by induction.
You need to use ##x > y## at this point. Your first and third term can be simplified. Also, in the formal proof you need to show the base case and mention ##p(k+1)##. I also noticed a minor typo with the ##a-b##, but I'm sure that is all it was.

Edit: You should change your ##n## variables to ##k## after introducing ##p(k)##.
 
  • #3
7
0
Yeah I'll show the base case and such details in the formal write up, it's really this step where I am stuck.

So I simplified it to:

k*x^(k+1)-k*y*x^k+x^(k+1)-y*x^k

What am I supposed to do with x>y?
 
Last edited:
  • #4
392
17
Try to do a substitution using ##x > y## so that two terms cancel out and you create an inequality. i.e. either plug in ##x## for ##y## or vice versa for one of the terms. The step after that is similar.
 
  • #5
7
0
can we say

k*x^(k+1)-k*y*x^k+x^(k+1)-y*x^k > k*x^(k+1)-k*y*x^k since x>y?
 
  • #6
392
17
can we say

k*x^(k+1)-k*y*x^k+x^(k+1)-y*x^k > k*x^(k+1)-k*y*x^k since x>y?
Absolutely. You substituted in ##y## for one of the ##x## in the ##+x^{k+1}## term so the result is smaller than the original equation (because you were adding the term) and then they canceled. Can you do something similar for the next step?
 
  • #7
7
0
I don't see what to do here. If we take k*x^(k+1)-k*y*x^k and did the same thing wouldn't we just get zero?
 
  • #8
392
17
Depending on the substitution you do, yes, you could end up with 0. That's obviously not what you want though. The goal in this proof by induction is to end up with the inequality ##\geq x^{k+1} - y^{k+1}##. What substitution can you do to make it look like that? (You aren't done just yet, almost there!)
 
  • #9
7
0
I suspected I should substitute y into x in the second term of kx^(k+1)-ky*x^k, but wouldn't that not work since we would be subtracting a smaller number than before?
 
Last edited:
  • #10
7
0
never mind, I figured it out. thanks for all your help!
 

Related Threads on Inductive proof

  • Last Post
Replies
6
Views
758
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
818
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
Top