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.
We have
$\displaystyle \alpha+ \beta = p+1$
and
$\displaystyle \alpha\beta = 1 $
$\displaystyle \alpha^{k+2} + \beta^{k+2} = (\alpha + \beta)(\alpha^{k+1} + \beta^{k+1}) - \alpha \beta(\alpha^{k} + \beta^{k})$
$\displaystyle \alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})$
$\displaystyle S_1$ and $\displaystyle S_2$ are true , now , assume $\displaystyle S_{k} $ and $\displaystyle S_{k+1} ~$ are also true .
Obviously , refering to the identity , $\displaystyle S_{k+2}~~$ are true
For part 2 , assume $\displaystyle S_{k-1} , S_{k} , S_{k+1} $ are true.
$\displaystyle \alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})$
To prove $\displaystyle S_{k+2}~$ is also true , we have to prove $\displaystyle A_{k+1} - A_{k}=/= 0mod(p)$ Where $\displaystyle A_k = \alpha^{k} + \beta^{k}$
$\displaystyle A_{k+1} - A_{k}= \alpha^{k+1} + \beta^{k+1} - \alpha^{k} - \beta^{k}$
$\displaystyle = \alpha^{k}(\alpha-1) + \beta^{k}(\beta - 1)$
$\displaystyle = \alpha^{k}(p-\beta) + \beta^{k}(p-\alpha)$
$\displaystyle = p(\alpha^{k} + \beta^{k}) - (\alpha \beta)( \alpha^{k-1} + \beta^{k-1})$
$\displaystyle = p(integer) + (\alpha^{k-1} + \beta^{k-1}) =/= 0mod(p)$
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 $\displaystyle \alpha+\beta$ and $\displaystyle \alpha\beta$ are integers.alpha x beta =1 ................(3)
Correct, and this is all you need, in order to show that $\displaystyle \alpha^2+\beta^2$ 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 $\displaystyle P(k+1)$ 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)}
$\displaystyle P(k+1) = P(k)(\alpha+\beta)-\alpha\beta P(k-1)$
So this, together with your assumptions that $\displaystyle P(k)$ and $\displaystyle P(k-1)$ are integers and the fact that $\displaystyle \alpha + \beta$ and $\displaystyle \alpha\beta$ are both integers is all you need to show that $\displaystyle P(k+1)$ is an integer.
Since you've already established that $\displaystyle P(1)$ and $\displaystyle P(2)$ 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
Part 2:
We know the following:
$\displaystyle \alpha + \beta = p + 1$
$\displaystyle \alpha\beta = 1$
$\displaystyle P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1})$.
So $\displaystyle P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})$
$\displaystyle = (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})$
Try dividing $\displaystyle P(k + 1)$ by $\displaystyle p$.
$\displaystyle \frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}$
$\displaystyle = \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}$.
Clearly $\displaystyle p + 1$ can not be divided by $\displaystyle p$ exactly, and you have already established that $\displaystyle \alpha^k + \beta^k$ and $\displaystyle \alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $\displaystyle p$, so $\displaystyle P(k + 1)$ can not be divided by $\displaystyle p$.
Q.E.D.
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 $\displaystyle p \ge 3$?)
I'm afraid ProveIt's last line doesn't work. Just because $\displaystyle \frac{A}{p}$ is not an integer and $\displaystyle \frac{B}{p}$ is not an integer doesn't necessarily mean that $\displaystyle \frac{A-B}{p}$ is not an integer.
May I suggest the following.
Using the notation $\displaystyle P(k) = \alpha^k +\beta^k$, and the proofs so far offered, we know that
$\displaystyle P(k+1) = (p+1)P(k) - P(k-1)$
$\displaystyle = pP(k) + P(k) - P(k-1)$
$\displaystyle \Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p$. Call this equation (1)
If we now replace $\displaystyle k$ by $\displaystyle (k-1)$ in this equation we get:
$\displaystyle P(k) \equiv P(k-1) - P(k-2) \mod p$
$\displaystyle \Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p$
$\displaystyle \Rightarrow P(k+1) \equiv -P(k-2) \mod p$
Therefore if $\displaystyle P(k-2)$ is not a multiple of $\displaystyle p$, then $\displaystyle P(k+1)$ isn't either.
So, provided $\displaystyle P(1), P(2)$ and $\displaystyle P(3)$ are not multiples of $\displaystyle p$, we have sufficient to show that $\displaystyle P(k)$ is not a multiple of $\displaystyle p$ for all integers $\displaystyle k \ge 1$.
$\displaystyle P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ is not a multiple of $\displaystyle p$
$\displaystyle P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$
$\displaystyle \Rightarrow P(2) \equiv (p-1) \mod p$
$\displaystyle \Rightarrow P(2) \ne 0 \mod p$, for $\displaystyle p \ge 2$
$\displaystyle P(3) \equiv P(2) - P(1) \mod p$ (using equation (1) with $\displaystyle k = 2$)
$\displaystyle \Rightarrow P(3) \equiv (p-1) - 1 \mod p$
$\displaystyle \Rightarrow P(3) \equiv (p-2) \mod p$
$\displaystyle \Rightarrow P(3) \ne 0 \mod p$, for $\displaystyle p\ge 3$
And that completes the proof, I think.
Grandad
Solution given by prove it(MHF contributor):
We know the following:
$\displaystyle \alpha + \beta = p + 1$
$\displaystyle \alpha\beta = 1$
$\displaystyle P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1})$.
So $\displaystyle P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})$
$\displaystyle = (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})$
Try dividing $\displaystyle P(k + 1)$ by $\displaystyle p$.
$\displaystyle \frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}$
$\displaystyle = \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}$.
Clearly $\displaystyle p + 1$ can not be divided by $\displaystyle p$ exactly, and you have already established that $\displaystyle \alpha^k + \beta^k$ and $\displaystyle \alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $\displaystyle p$, so $\displaystyle P(k + 1)$ can not be divided by $\displaystyle p$.
The problem of the question lies HERE.
It is true that $\displaystyle \alpha^k + \beta^k$ and $\displaystyle \alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $\displaystyle p$
------------------------------------------------------------------------------------------------
But you can not say that the difference between $\displaystyle \alpha^k + \beta^k$ and $\displaystyle \alpha^{k - 1} + \beta^{k - 1}$
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, $\displaystyle A, B, ...$ are integers.
$\displaystyle P(k+1) = (p+1)P(k) - P(k-1)$
$\displaystyle = pP(k) + P(k) - P(k-1)$
$\displaystyle \Rightarrow P(k+1) =Ap+ P(k)-P(k-1)$. Call this equation (1)
If we now replace $\displaystyle k$ by $\displaystyle (k-1)$ in this equation we get:
$\displaystyle P(k) = Bp+P(k-1) - P(k-2) $
$\displaystyle \Rightarrow P(k+1) =(A+B)p +P(k-1) - P(k-2) - P(k-1)$
$\displaystyle \Rightarrow P(k+1) =(A+B)p -P(k-2)$
Therefore if $\displaystyle P(k-2)$ is not a multiple of $\displaystyle p$, then $\displaystyle P(k+1)$ isn't either.
So, provided $\displaystyle P(1), P(2)$ and $\displaystyle P(3)$ are not multiples of $\displaystyle p$, we have sufficient to show that $\displaystyle P(k)$ is not a multiple of $\displaystyle p$ for all integers $\displaystyle k \ge 1$.
$\displaystyle P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ leaves a remainder $\displaystyle 1$ when divided by $\displaystyle p$.
$\displaystyle P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$
$\displaystyle \Rightarrow P(2) =Cp+ (p-1) $
$\displaystyle \Rightarrow P(2)$ leaves a remainder $\displaystyle (p-1)> 0$, for $\displaystyle p \ge 2$
$\displaystyle P(3) = Dp+ P(2) - P(1)$ (using equation (1) with $\displaystyle k = 2$)
$\displaystyle \Rightarrow P(3) = (C+D)p + (p-1) - (p+1)$
$\displaystyle \Rightarrow P(3) = (C+D-1)p + (p - 2)$
$\displaystyle \Rightarrow P(3)$ leaves a remainder $\displaystyle (p-2) > 0$, for $\displaystyle p \ge 3$, when divided by $\displaystyle p$.
That completes the proof.
Grandad