induction q (1 Viewer)

notme123

Well-Known Member
Joined
Apr 14, 2020
Messages
1,002
Gender
Male
HSC
2021
just saying no way this would be a hsc question. their solutions are always neat and tidy and less than a page
 

Eagle Mum

Well-Known Member
Joined
Nov 9, 2020
Messages
532
Gender
Female
HSC
N/A
x^n-y^n factorisation where u pull out something to make 85
ye still dont see it
x^n-y^n is divisible by (x-y) There’s a different induction proof for this.

Therefore, 17(33^n-28^n) + 5(28^n-11^n) = 17*(33-28)*N1 + 5(28-11)*N2 = 17*5N1 + 5*17N2 = 85(N1 + N2)
In an induction proof, the first component of the algebraic expression is assumed to be divisible by 85.
 
Last edited:

notme123

Well-Known Member
Joined
Apr 14, 2020
Messages
1,002
Gender
Male
HSC
2021
x^n-y^n is divisible by (x-y) There’s a different induction proof for this.

Therefore, 17(33^n-28^n) + 5(28^n-11^n) = 17*(33-28)*N1 + 5(28-11)*N2 = 17*5N1 + 5*17N2 = 85(N1 + N2)
In an induction proof, the first component of the algebraic expression is assumed to be divisible by 85.
genius
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
A similar approach...

Result (A)

It follows that is divisible by for all positive integers .

Corollaries of Result (A)
  • is divisible by .
  • is divisible by .
Thus, is also divisible by 17.

HAHS Proof 1
  • is divisible by .
  • is divisible by .
Thus, is also divisible by 5.

Having proven the given result is divisible by both 17 and 5, and since these numbers are coprime, it immediately follows that the statement is also divisible by .

I didn't notice the proof of divisibility by 5, however, and proceeded instead to prove that the statement is divisible by 5 another way:

Re-casting the induction proof approach:
It follows from above that I seek to prove that:
  • Defining and , I seek that is divisible by 85.
  • It has been established that is divisible by 17, and that I only need to be divisible by 5.

And, by similar reasoning, where .

Note further that and that .




The core part of the proof by induction will have as the induction hypothesis that


and the working will establish that


NOTES:
  1. As an induction problem, this is too hard to be reasonable as a test of MX2 content.
  2. The assumption that this is an induction problem is just that - an assumption. This question illustrates a comment that I have made before, that the Proof section of the new syllabus offers opportunities to ask very difficult questions and the extent of this will be explored over years to come.
  3. Splitting into in the induction part uses the same idea / approach as is key in @idkkdi's very concise proof above
  4. The question could just have easily asked for a proof that the result is divisible by 170, as this is obviously follows once the divisibility by 85 is established.
 

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
A similar approach...

Result (A)

It follows that is divisible by for all positive integers .

Corollaries of Result (A)
  • is divisible by .
  • is divisible by .
Thus, is also divisible by 17.

HAHS Proof 1
  • is divisible by .
  • is divisible by .
Thus, is also divisible by 5.

Having proven the given result is divisible by both 17 and 5, and since these numbers are coprime, it immediately follows that the statement is also divisible by .

I didn't notice the proof of divisibility by 5, however, and proceeded instead to prove that the statement is divisible by 5 another way:

Re-casting the induction proof approach:
It follows from above that I seek to prove that:
  • Defining and , I seek that is divisible by 85.
  • It has been established that is divisible by 17, and that I only need to be divisible by 5.

And, by similar reasoning, where .

Note further that and that .




The core part of the proof by induction will have as the induction hypothesis that


and the working will establish that


NOTES:
  1. As an induction problem, this is too hard to be reasonable as a test of MX2 content.
  2. The assumption that this is an induction problem is just that - an assumption. This question illustrates a comment that I have made before, that the Proof section of the new syllabus offers opportunities to ask very difficult questions and the extent of this will be explored over years to come.
  3. Splitting into in the induction part uses the same idea / approach as is key in @idkkdi's very concise proof above
  4. The question could just have easily asked for a proof that the result is divisible by 170, as this is obviously follows once the divisibility by 85 is established.

1632038119147.png
nvm, was being dumb.
 
Last edited:

stupid_girl

Active Member
Joined
Dec 6, 2009
Messages
221
Gender
Undisclosed
HSC
N/A
View attachment 32200
do this since ur so smart
This is essentially a watered-down version of another question that I had seen before.
Prove that 2903^n – 803^n – 464^n + 261^n is divisible by 1897 for any positive integers.

This kind of problem can be solved by number theory in a much more elegant way. It is just not worthwhile to restrict yourself to MI and spend ages on some messy algebra like this.
5CC2D923-D8AE-4ECC-9528-1BEC1C2802AF.jpeg
 
Last edited:

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
This is essentially a watered-down version of another question that I had seen before.
Prove that 2903^n – 803^n – 464^n + 261^n is divisible by 1897 for any positive integers.

This kind of problem can be solved by number theory in a much more elegant way. It is just not worthwhile to restrict yourself to MI and spend ages on some messy algebra like this.
View attachment 32214
can we get an admin to change her name?
 

Talia_02

New Member
Joined
Sep 19, 2021
Messages
4
Gender
Female
HSC
2022
Check out James Ruse 2018 Paper. I swear there was something similar!
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
just something to add,

View attachment 32213
result A only holds true for n, where n is odd.

probably need to take either two cases, or a more general proof.
Are you sure?

Certainly the factorisation of only works for odd (as then , allowing the above factorisation to be used).

However, I am not seeing any flaw in the reasoning that I have used that falisfies the result for the case where is even and the result is certainly true for:




What do you think is wrong with my proof / reasoning?
 

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
Are you sure?

Certainly the factorisation of only works for odd (as then , allowing the above factorisation to be used).

However, I am not seeing any flaw in the reasoning that I have used that falisfies the result for the case where is even and the result is certainly true for:




What do you think is wrong with my proof / reasoning?
was mixing it up with x^n+y^n which doesn't work for even.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top