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

Printable View

- Jul 4th 2009, 05:21 AMmatsci0000Mathematical 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 AMmatsci0000Please 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]*, alpha^k +beta^k is an integer and alpha^(k-1) +beta^(k-1) is also an integer.

and alpha^(k-1)+beta^(k-1)

From induction assumption

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 AMmatsci0000
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 a**lpha 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.(Headbang)

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 PMsimplependulum

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 AMGrandadFirst part of your solution
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:

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

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

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

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)

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

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

Grandad - Jul 5th 2009, 01:22 AMProve 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 AMGrandadInduction 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.

Grandad - Jul 5th 2009, 09:35 AMmatsci0000Argument
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 PMmatsci0000
- Jul 8th 2009, 12:27 AMGrandadModular arithmetic
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