Let p greater than or equal to 3 be an integer.Alpha and beta are the roots of x^2-(p+1)x+1=0.Using mathematical induction ,prove that alpha^n+beta^n
1)is an integer
2)is not divisible by p
I've solved the first part of the question in the following way(with the help of second hypothesis):
Given :x^2-(p+1)x+1=0 and alpha and beta are the roots .
so, alpha+beta = p+1 ..............(1) and alpha+beta is greater than or equal to 4.............(2){since it is given that p>=3}
alpha x beta =1 ................(3)
STEP1 -- To prove that P(1) is an integer.
alpha^1+beta^1 =alpha+beta -------> is an integer. [from (1)]
To prove that P(2) is an integer.
P(2)=alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta
{(alpha+beta)^2 is >=16 [from 2] , 2alpha .beta =2 [from 3]
so, the value of alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta becomes >=14 and hence it is an integer.}
STEP 2 INDUCTION ASSUMPTION
--------------------------------
Let P(k) be an integer.
so, alpha^k +beta^k be an integer.
Let P(k-1) be an integer.
so,alpha^(k-1) +beta^(k-1) be an integer.
Step3 -- To prove that P(k+1) is an integer.
P(k)=alpha^(k+1) +beta^(k+1)
=(alpha^k +beta^k )(alpha+beta) - alpha^k.beta-beta^k.alpha
=(alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)}
USING-
alpha+beta is greater than or equal to 4.............(2)
alpha x beta =1 ................(3)
(alpha^k +beta^k )(alpha+beta) >=4 [from above 2 relations]
and alpha^(k-1)+beta^(k-1)
From induction assumption , alpha^k +beta^k is an integer and alpha^(k-1) +beta^(k-1) is also an integer.
Hence it has been proved that (alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)} is an integer.
I've solved the second part by second hypothesis of induction.
alpha + beta= p+1
this implies that alpha+beta is not divisible by p...........(1)
and alpha x beta=1 .............(2)
STEP1 -- To prove that P(1) is not divisible by p.
alpha^1+beta^1=alpha+beta is not divisible by p.[from (1)]
To prove that P(2) is not divisible by p.
alpha^2+beta^2=(alpha+beta)^2 - 2 .alpha beta is not divisible by p
STEP2(INDUCTION ASSUMPTION) -- Let P(k) and P(k-1) be true.
so, alpha^k+beta^k is not divisible by p. ............(3)
and alpha^(k-1)+beta^(k-1) is not divisible by p..............(4)
STEP3 -- To prove that P(k+1) is not divisible by p.
P(k+1)=alpha^(k+1)+beta^(k+1)
=(alpha^k+beta^k)(alpha+beta) - alpha^kbeta -beta.alpha^k
=(alpha^k+beta^k)(alpha+beta) - alpha.beta{alpha^(k-1)+beta^(k-1)}
from(INDUCTION ASSUMPTION)
alpha^k+beta^k is not divisible by p............(3)
and alpha^(k-1)+beta^(k-1) is not divisible by p..............(4)
I'm stuck at this point.
then, how to prove (alpha^k+beta^k)(alpha+beta) - alpha.beta{alpha^(k-1)+beta^(k-1)} is not divisible by p.
I've solved this question many times but haven't proved it perfectly.
Hello matsci0000
Thanks for showing us your working. This part is pretty well OK, except for where I've commented. Correct. But you don't need this bit:
and alpha+beta is greater than or equal to 4.............(2){since it is given that p>=3}
Correct. Notice that this now shows that and are integers.alpha x beta =1 ................(3)
Correct, and this is all you need, in order to show that is an integer. So you don't need this bit:STEP1 -- To prove that P(1) is an integer.
alpha^1+beta^1 =alpha+beta -------> is an integer. [from (1)]
To prove that P(2) is an integer.
P(2)=alpha^2+beta^2=(alpha+beta)^2- 2alpha .betaNow for the next part:{(alpha+beta)^2 is >=16 [from 2] , 2alpha .beta =2 [from 3]
so, the value of alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta becomes >=14 and hence it is an integer.}You mean here, of course.STEP 2 INDUCTION ASSUMPTION
--------------------------------
Let P(k) be an integer.
so, alpha^k +beta^k be an integer.
Let P(k-1) be an integer.
so,alpha^(k-1) +beta^(k-1) be an integer.
Step3 -- To prove that P(k+1) is an integer.
P(k)=alpha^(k+1) +beta^(k+1)
This is fine. In other words=(alpha^k +beta^k )(alpha+beta) - alpha^k.beta-beta^k.alpha
=(alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)}
So this, together with your assumptions that and are integers and the fact that and are both integers is all you need to show that is an integer.
Since you've already established that and are integers, this completes the proof.
So you don't need this bit:
USING-
alpha+beta is greater than or equal to 4.............(2)
alpha x beta =1 ................(3)
(alpha^k +beta^k )(alpha+beta) >=4 [from above 2 relations]
and alpha^(k-1)+beta^(k-1)
I haven't time now to look at your proof of part 2. If no-one else has commented on it, I'll do so later.
Grandad
Hello everyone -
I don't think any of the proofs so far are really complete, although simplependulum has all but done it - without adequately testing the initial hypotheses. (Where, for instance, is the requirement that ?)
I'm afraid ProveIt's last line doesn't work. Just because is not an integer and is not an integer doesn't necessarily mean that is not an integer.
May I suggest the following.
Using the notation , and the proofs so far offered, we know that
. Call this equation (1)
If we now replace by in this equation we get:
Therefore if is not a multiple of , then isn't either.
So, provided and are not multiples of , we have sufficient to show that is not a multiple of for all integers .
is not a multiple of
, for
(using equation (1) with )
, for
And that completes the proof, I think.
Grandad
Solution given by prove it(MHF contributor):
We know the following:
.
So
Try dividing by .
.
Clearly can not be divided by exactly, and you have already established that and are not divisible by , so can not be divided by .
The problem of the question lies HERE.
It is true that and are not divisible by
------------------------------------------------------------------------------------------------
But you can not say that the difference between and
is not divisible by p.
The above argument given by me can be more clear from the following example-
7 is not divisible by 3 and 4 is also not divisible by 3
But their difference which is equal to 3 is divisible by 3.
Hello matsci0000Yes. The modular arithmetic notation I used is a convenient way of discussing remainders when one integer is divided by another. But instead of using the mod notation, we can write the proof out as follows (it just looks a bit more complicated, that's all).
In the proof that follows, are integers.
. Call this equation (1)
If we now replace by in this equation we get:
Therefore if is not a multiple of , then isn't either.
So, provided and are not multiples of , we have sufficient to show that is not a multiple of for all integers .
leaves a remainder when divided by .
leaves a remainder , for
(using equation (1) with )
leaves a remainder , for , when divided by .
That completes the proof.
Grandad