• Support PF! Buy your school textbooks, materials and every day products Here!

Induction seems to not work?

  • #1
rock.freak667
Homework Helper
6,230
31

Homework Statement



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

Homework Equations





The Attempt at a Solution



Assume true for n=N

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

[tex] \times (23^2 + 31^2)[/tex]

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


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

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

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #3
378
2
Code:
[tex]23^{2N}+31^{2N}+46=48A[/tex]
correct

[tex] \times (23^2 + 31^2)[/tex]
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 ..
 
  • #4
378
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
 
  • #5
rock.freak667
Homework Helper
6,230
31
Code:
[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 [itex]23^2+31^2[/itex] so could get [itex]23^{2N+2}+31^{2N+2}[/itex]

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 definately don't know what you are talking about since I never learnt that.
 
  • #6
378
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


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
 
  • #7
rock.freak667
Homework Helper
6,230
31
So I am supposed to just substitute n=N+1 instead of building the (N+1)th term?
 
  • #8
378
2
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
 
  • #9
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #10
HallsofIvy
Science Advisor
Homework Helper
41,794
925
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 definately don't know what you are talking about since I never learnt that.
232= 529= 11(48)+ 1, 312= 961= 20(48)+ 1
So each has a remainder of one when divided by 48.

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

Related Threads for: Induction seems to not work?

Replies
3
Views
562
Replies
8
Views
2K
Replies
18
Views
1K
Replies
6
Views
3K
Replies
2
Views
449
Replies
11
Views
1K
  • Last Post
Replies
2
Views
672
Top