Mathematical Induction

matsci0000 · #1 $Old$ July 4th, 2009, 07:21 AM

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

matsci0000 · #2 $Old$ July 4th, 2009, 07:48 AM

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.

matsci0000 · #3 $Old$ July 4th, 2009, 08:05 AM

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.

simplependulum · #4 $Old$ July 5th, 2009, 12:23 AM

Quote:

Originally Posted by matsci0000 $View Post$

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

$\alpha+ \beta = p+1$
and
$\alpha\beta = 1$

$\alpha^{k+2} + \beta^{k+2} = (\alpha + \beta)(\alpha^{k+1} + \beta^{k+1}) - \alpha \beta(\alpha^{k} + \beta^{k})$

$\alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})$

$S_1$ and $S_2$ are true , now , assume $S_{k}$ and $S_{k+1} ~$ are also true .

Obviously , refering to the identity , $S_{k+2}~~$ are true

For part 2 , assume $S_{k-1} , S_{k} , S_{k+1}$ are true.

$\alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})$

To prove $S_{k+2}~$ is also true , we have to prove $A_{k+1} - A_{k}=/= 0mod(p)$ Where $A_k = \alpha^{k} + \beta^{k}$

$A_{k+1} - A_{k}= \alpha^{k+1} + \beta^{k+1} - \alpha^{k} - \beta^{k}$

$= \alpha^{k}(\alpha-1) + \beta^{k}(\beta - 1)$
$= \alpha^{k}(p-\beta) + \beta^{k}(p-\alpha)$
$= p(\alpha^{k} + \beta^{k}) - (\alpha \beta)( \alpha^{k-1} + \beta^{k-1})$
$= p(integer) + (\alpha^{k-1} + \beta^{k-1}) =/= 0mod(p)$

Grandad · #5 $Old$ July 5th, 2009, 03:07 AM

Hello matsci0000

Thanks for showing us your working. This part is pretty well OK, except for where I've commented.

Quote:

Originally Posted by matsci0000 $View Post$

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:

Quote:

and alpha+beta is greater than or equal to 4.............(2){since it is given that p>=3}

Quote:

alpha x beta =1 ................(3)

Correct. Notice that this now shows that $\alpha+\beta$ and $\alpha\beta$ are integers.

Quote:

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 $\alpha^2+\beta^2$ is an integer. So you don't need this bit:

Quote:

{(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:

Quote:

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 $P(k+1)$ here, of course.

Quote:

=(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

$P(k+1) = P(k)(\alpha+\beta)-\alpha\beta P(k-1)$

So this, together with your assumptions that $P(k)$ and $P(k-1)$ are integers and the fact that $\alpha + \beta$ and $\alpha\beta$ are both integers is all you need to show that $P(k+1)$ is an integer.

Since you've already established that $P(1)$ and $P(2)$ are integers, this completes the proof.

So you don't need this bit:

Quote:

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

Prove It · #6 $Old$ July 5th, 2009, 03:22 AM

Part 2:

We know the following:

$\alpha + \beta = p + 1$

$\alpha\beta = 1$

$P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1})$ .

So $P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})$

$= (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})$

Try dividing $P(k + 1)$ by $p$ .

$\frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}$

$= \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}$ .

Clearly $p + 1$ can not be divided by $p$ exactly, and you have already established that $\alpha^k + \beta^k$ and $\alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $p$ , so $P(k + 1)$ can not be divided by $p$ .

Q.E.D.

Grandad · #7 $Old$ July 5th, 2009, 07:24 AM

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 $p \ge 3$ ?)

I'm afraid ProveIt's last line doesn't work. Just because $\frac{A}{p}$ is not an integer and $\frac{B}{p}$ is not an integer doesn't necessarily mean that $\frac{A-B}{p}$ is not an integer.

May I suggest the following.

Using the notation $P(k) = \alpha^k +\beta^k$ , and the proofs so far offered, we know that

$P(k+1) = (p+1)P(k) - P(k-1)$

$= pP(k) + P(k) - P(k-1)$

$\Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p$ . Call this equation (1)

If we now replace $k$ by $(k-1)$ in this equation we get:

$P(k) \equiv P(k-1) - P(k-2) \mod p$

$\Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p$

$\Rightarrow P(k+1) \equiv -P(k-2) \mod p$

Therefore if $P(k-2)$ is not a multiple of $p$ , then $P(k+1)$ isn't either.

So, provided $P(1), P(2)$ and $P(3)$ are not multiples of $p$ , we have sufficient to show that $P(k)$ is not a multiple of $p$ for all integers $k \ge 1$ .

$P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ is not a multiple of $p$

$P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$

$\Rightarrow P(2) \equiv (p-1) \mod p$

$\Rightarrow P(2) \ne 0 \mod p$ , for $p \ge 2$

$P(3) \equiv P(2) - P(1) \mod p$ (using equation (1) with $k = 2$ )

$\Rightarrow P(3) \equiv (p-1) - 1 \mod p$

$\Rightarrow P(3) \equiv (p-2) \mod p$

$\Rightarrow P(3) \ne 0 \mod p$ , for $p\ge 3$

And that completes the proof, I think.

Grandad

matsci0000 · #8 $Old$ July 5th, 2009, 11:35 AM

Solution given by prove it(MHF contributor):
We know the following:

$\alpha + \beta = p + 1$

$\alpha\beta = 1$

$P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1})$ .

So $P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})$

$= (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})$

Try dividing $P(k + 1)$ by $p$ .

$\frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}$

$= \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}$ .

Clearly $p + 1$ can not be divided by $p$ exactly, and you have already established that $\alpha^k + \beta^k$ and $\alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $p$ , so $P(k + 1)$ can not be divided by $p$ .
The problem of the question lies HERE.
It is true that $\alpha^k + \beta^k$ and $\alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $p$
------------------------------------------------------------------------------------------------

But you can not say that the difference between $\alpha^k + \beta^k$ and $\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.

matsci0000 · #9 $Old$ July 7th, 2009, 07:59 PM

Quote:

Originally Posted by Grandad $View Post$

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 $p \ge 3$ ?)

I'm afraid ProveIt's last line doesn't work. Just because $\frac{A}{p}$ is not an integer and $\frac{B}{p}$ is not an integer doesn't necessarily mean that $\frac{A-B}{p}$ is not an integer.

May I suggest the following.

Using the notation $P(k) = \alpha^k +\beta^k$ , and the proofs so far offered, we know that

$P(k+1) = (p+1)P(k) - P(k-1)$

$= pP(k) + P(k) - P(k-1)$

$\Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p$ . Call this equation (1)

If we now replace $k$ by $(k-1)$ in this equation we get:

$P(k) \equiv P(k-1) - P(k-2) \mod p$

$\Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p$

$\Rightarrow P(k+1) \equiv -P(k-2) \mod p$

Therefore if $P(k-2)$ is not a multiple of $p$ , then $P(k+1)$ isn't either.

So, provided $P(1), P(2)$ and $P(3)$ are not multiples of $p$ , we have sufficient to show that $P(k)$ is not a multiple of $p$ for all integers $k \ge 1$ .

$P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ is not a multiple of $p$

$P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$

$\Rightarrow P(2) \equiv (p-1) \mod p$

$\Rightarrow P(2) \ne 0 \mod p$ , for $p \ge 2$

$P(3) \equiv P(2) - P(1) \mod p$ (using equation (1) with $k = 2$ )

$\Rightarrow P(3) \equiv (p-1) - 1 \mod p$

$\Rightarrow P(3) \equiv (p-2) \mod p$

$\Rightarrow P(3) \ne 0 \mod p$ , for $p\ge 3$

And that completes the proof, I think.

Grandad

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

Grandad · #10 $Old$ July 8th, 2009, 02:27 AM

Hello matsci0000

Quote:

Originally Posted by matsci0000 $View Post$

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, $A, B, ...$ are integers.

$P(k+1) = (p+1)P(k) - P(k-1)$

$= pP(k) + P(k) - P(k-1)$

$\Rightarrow P(k+1) =Ap+ P(k)-P(k-1)$ . Call this equation (1)

If we now replace $k$ by $(k-1)$ in this equation we get:

$P(k) = Bp+P(k-1) - P(k-2)$

$\Rightarrow P(k+1) =(A+B)p +P(k-1) - P(k-2) - P(k-1)$

$\Rightarrow P(k+1) =(A+B)p -P(k-2)$

Therefore if $P(k-2)$ is not a multiple of $p$ , then $P(k+1)$ isn't either.

So, provided $P(1), P(2)$ and $P(3)$ are not multiples of $p$ , we have sufficient to show that $P(k)$ is not a multiple of $p$ for all integers $k \ge 1$ .

$P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ leaves a remainder $1$ when divided by $p$ .

$P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$

$\Rightarrow P(2) =Cp+ (p-1)$

$\Rightarrow P(2)$ leaves a remainder $(p-1)> 0$ , for $p \ge 2$

$P(3) = Dp+ P(2) - P(1)$ (using equation (1) with $k = 2$ )

$\Rightarrow P(3) = (C+D)p + (p-1) - (p+1)$

$\Rightarrow P(3) = (C+D-1)p + (p - 2)$

$\Rightarrow P(3)$ leaves a remainder $(p-2) > 0$ , for $p \ge 3$ , when divided by $p$ .

That completes the proof.

Grandad