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

So this, together with your assumptions that and are integers and the fact that and are both integers is all you need to show that is an integer.

Since you've already established that and 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:

.

So

Try dividing by .

.

Clearly can not be divided by exactly, and you have already established that and are not divisible by , so can not be divided by .

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

I'm afraid ProveIt's last line doesn't work. Just because is not an integer and is not an integer doesn't necessarily mean that is not an integer.

May I suggest the following.

Using the notation , and the proofs so far offered, we know that

. Call this equation (1)

If we now replace by in this equation we get:

Therefore if is not a multiple of , then isn't either.

So, provided and are not multiples of , we have sufficient to show that is not a multiple of for all integers .

is not a multiple of

, for

(using equation (1) with )

, for

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:

.

So

Try dividing by .

.

Clearly can not be divided by exactly, and you have already established that and are not divisible by , so can not be divided by .

The problem of the question lies HERE.

It is true that and are not divisible by

------------------------------------------------------------------------------------------------

But you can not say that the difference between and

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

. Call this equation (1)

If we now replace by in this equation we get:

Therefore if is not a multiple of , then isn't either.

So, provided and are not multiples of , we have sufficient to show that is not a multiple of for all integers .

leaves a remainder when divided by .

leaves a remainder , for

(using equation (1) with )

leaves a remainder , for , when divided by .

That completes the proof.

Grandad