# Mathematical Induction

• Jul 4th 2009, 05:21 AM
matsci0000
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
• Jul 4th 2009, 05:48 AM
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) 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.
• Jul 4th 2009, 06:05 AM
matsci0000
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)

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.
• Jul 4th 2009, 10:23 PM
simplependulum
Quote:

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)$
• Jul 5th 2009, 01: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
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 $\displaystyle \alpha+\beta$ and $\displaystyle \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 $\displaystyle \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 $\displaystyle 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

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

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.

• Jul 5th 2009, 01:22 AM
Prove It
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.
• Jul 5th 2009, 05:24 AM
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.

• Jul 5th 2009, 09:35 AM
matsci0000
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.
• Jul 7th 2009, 05:59 PM
matsci0000
Quote:

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?
• Jul 8th 2009, 12:27 AM
Modular arithmetic
Hello matsci0000
Quote:

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.