Is Induction Effective for Proving Divisibility by 48 in Mathematical Sequences?

[rock.freak667]

Homework Statement

Prove by mathematical induction,or otherwise,that 23^{2n}+31^{2n}+46 is divisible by 48 for all n \geq 0

Homework Equations

The Attempt at a Solution

Assume true for n=N

23^{2N}+31^{2N}+46=48A

\times (23^2 + 31^2)

23^{2N+2}+31^{2N+2}+46(23^2 + 31^2)+23^2(31^{2N})+31^2(23^{2N})=48A(23^2 + 31^2)


23^{2N+2}+31^{2N+2}+68540+31^{2N}(528+1)+23^{2N}(960+1)=48A(23^2 + 31^2)

Simplifying gives me what I need, i.e. things divible by 48, but 68540 is not...any suggestions?

 

[Dick]

Everything is not supposed to be divisible by 48. You can drop the things that are, of course. Now you just want to show 68540+31^(2N)+23^(2N) gives a remainder of 46 when divided by 48. BTW, it's easier without induction. Just observe 23^2 and 31^2 are both equal to 1 mod 48.

 

[rootX]

[tex]23^{2N}+31^{2N}+46=48A[/tex]

correct

\times (23^2 + 31^2)

what's this doing there? if this is a part of the first equation ...


at n+1:
23^(2n)*23^2 + 31^(2n)*31^2+46

now trying writing this in orginal form:

23^(2n)*528 + 23^(2n) + 31^(2n)*31^2+46

do same for 31 ..

 

[rootX]

since you already got the answer.. here's what I did:

23^(2n)*528 + 23^(2n) + 31^(2n)*960 + 31 ^(2n) +46

= {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

everything divisible by 48

 

[rock.freak667]

[tex]23^{2N}+31^{2N}+46=48A[/tex]

correct



what's this doing there? if this is a part of the first equation ...


at n+1:
23^(2n)*23^2 + 31^(2n)*31^2+46

now trying writing this in orginal form:

23^(2n)*528 + 23^(2n) + 31^(2n)*31^2+46

do same for 31 ..

Well I multiplied what I assumed to be true by 23^2+31^2 so could get 23^{2N+2}+31^{2N+2}

since you already got the answer.. here's what I did:

23^(2n)*528 + 23^(2n) + 31^(2n)*960 + 31 ^(2n) +46

= {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

everything divisible by 48

wouldn't I need to show that everything is divisible by 48 for it to be true,hence why I can't show 68540 is divisible by 48.

Everything is not supposed to be divisible by 48. You can drop the things that are, of course. Now you just want to show 68540+31^(2N)+23^(2N) gives a remainder of 46 when divided by 48. BTW, it's easier without induction. Just observe 23^2 and 31^2 are both equal to 1 mod 48.

I don't get how I am supposed to show it gives a remaineder of 48, when in the inductive hypothesis, I assumed that everything was together was divisible by 48.

Also,I don't understand what 1 mod 48 means. If it has to do with modular arithmetic,then I definitely don't know what you are talking about since I never learned that.

 

[rootX]

since you already got the answer.. here's what I did:

23^(2n)*528 + 23^(2n) + 31^(2n)*960 + 31 ^(2n) +46

= {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

everything divisible by 48


wouldn't I need to show that everything is divisible by 48 for it to be true

Over there, from induction you assumed that {23^(2n) + 31 ^(2n) +46} is divisible by 48

at n+1 .. you get {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

divide this by 48..
{23^(2n) + 31 ^(2n) +46} is divisible
23^(2n)*528 is divisible
31^(2n)*960 is divisible...

so everything is proved

 

[rock.freak667]

So I am supposed to just substitute n=N+1 instead of building the (N+1)th term?

 

[rootX]

So I am supposed to just substitute n=N+1 instead of building the (N+1)th term?

yep, isn't this is what you do for induction?

first assume it is true for n
and then substitute n by n+1 .. and prove it is true

 

[Dick]

You really already have it, you just don't seem to see it. According to your inductive hypothesis, if you divide 23^(2N)+31^(2N) by 48, what is the remainder? Now look at the N+1 case. Assuming the hypothesis what's the remainder of 23^(2N+2)+31^(2N+2) divided by 48?

 

[HallsofIvy]

I don't get how I am supposed to show it gives a remaineder of 48, when in the inductive hypothesis, I assumed that everything was together was divisible by 48.

He didn't say "remainder of 48", he said remainder of 46- so that added to the other remainders, they add up to 48.

Also,I don't understand what 1 mod 48 means. If it has to do with modular arithmetic,then I definitely don't know what you are talking about since I never learned that.

23²= 529= 11(48)+ 1, 31²= 961= 20(48)+ 1
So each has a remainder of one when divided by 48.

Also (x+ 1)ⁿ= a string of things times powers of x + 1 and so has a remainder of 1 when divided by x. Both 23²ⁿ and 31²ⁿ have a remainder of 1 when divided by 48 for any n.