1. ## Mathematical Induction

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

2. ## Please check my solution

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.

3. 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.

4. Originally Posted by matsci0000
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

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)$

5. ## First part of your solution

Hello matsci0000

Thanks for showing us your working. This part is pretty well OK, except for where I've commented.
Originally Posted by matsci0000
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)
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}

alpha x beta =1 ................(3)
Correct. Notice that this now shows that $\displaystyle \alpha+\beta$ and $\displaystyle \alpha\beta$ are integers.

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
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:
{(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.}
Now for the next part:
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)
You mean $\displaystyle P(k+1)$ here, of course.
=(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)}
This is fine. In other words

$\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.

6. 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.

7. ## Induction proof - part 2

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.

8. ## Argument

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 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.

Thanks Grandad for the proof but I do not know anything about modulus and its operations.Is there any other alternate solution for this?

10. ## Modular arithmetic

Hello matsci0000
Originally Posted by matsci0000
Thanks Grandad for the proof but I do not know anything about modulus and its operations.Is there any other alternate solution for this?
Yes. 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.