induction q (1 Viewer)

notme123 · Sep 18, 2021

just saying no way this would be a hsc question. their solutions are always neat and tidy and less than a page

idkkdi · Sep 18, 2021

mr.habibbi said:
View attachment 32200
do this since ur so smart

33^n+1 - 16^n+1 - 28^n+1 + 11^n+1
=16(33^n-16^n-28^n+11^n) + 17(33^n-28^n) + 5(28^n-11^n)
= not bothered to type out
= 85k

Life'sHard · Sep 18, 2021

idkkdi said:
33^n+1 - 16^n+1 - 28^n+1 + 11^n+1
=16(33^n-16^n-28^n+11^n) + 17(33^n-28^n) + 5(28^n-11^n)
= not bothered to type out
= 85k

Lmao

notme123 · Sep 18, 2021

idkkdi said:
33^n+1 - 16^n+1 - 28^n+1 + 11^n+1
=16(33^n-16^n-28^n+11^n) + 17(33^n-28^n) + 5(28^n-11^n)
= not bothered to type out
= 85k

1, 2 skip a few 99, 100

idkkdi · Sep 19, 2021

notme123 said:
1, 2 skip a few 99, 100

x^n-y^n factorisation where u pull out something to make 85

notme123 · Sep 19, 2021

idkkdi said:
x^n-y^n factorisation where u pull out something to make 85

ye still dont see it

Eagle Mum · Sep 19, 2021

idkkdi said:
x^n-y^n factorisation where u pull out something to make 85

notme123 said:
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.

notme123 · Sep 19, 2021

Eagle Mum said:
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

Eagle Mum · Sep 19, 2021

notme123 said:
genius

All credit @idkkdi.
I just filled in some details since he's probably busy studying for the HSC.

CM_Tutor · Sep 19, 2021

A similar approach...

Result (A)

$\begin{align*} \textbf{Theorem:} \qquad x^n - y^n &= (x - y)\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \quad \text{for positive integers $n$} \\ \\ \textbf{Proof:} \qquad \text{RHS}\ &= (x - y)\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \\ &= x\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) - y\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \\ &= x^n + x^{n-1}y + x^{n-2}y^2 + ... + xy^{n-1} - \left(x^{n-1}y + x^{n-2}y^2 + x^{n-3}y^3 + ... + y^n\right) \\ &= x^n + \left(x^{n-1}y - x^{n-1}y\right) + \left(x^{n-2}y^2 - x^{n-2}y^2\right) + ... + \left(xy^{n-1} - xy^{n-1}\right) - y^n \\ &= x^n - y^n \\ &= \text{LHS} \end{align*}$

It follows that $x^n - y^n$ is divisible by $x - y$ for all positive integers $n$ .

Corollaries of Result (A)

$33^n - 16^n$ is divisible by $33-16=17$ .
$28^n - 11^n$ is divisible by $28-11=17$ .

Thus, $33^n - 16^n - 28^n + 11^n = 33^n - 16^n - \left(28^n - 11^n\right)$ is also divisible by 17.

HAHS Proof 1

$33^n - 28^n$ is divisible by $33-28=5$ .
$16^n - 11^n$ is divisible by $16-11=5$ .

Thus, $33^n - 16^n - 28^n + 11^n = 33^n - 28^n - \left(16^n - 11^n\right)$ 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 $17 \times 5 = 85$ .

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 $X_n = 33^n - 16^n$ and $Y_n = 28^n - 11^n$ , I seek that $A_n = X_n - Y_n$ is divisible by 85.
It has been established that $A_n$ is divisible by 17, and that I only need $A_n$ to be divisible by 5.

$\begin{align*} X_{n+1} &= 33^{n+1} - 16^{n+1} \qquad \qquad \text{by definition} \\ &= 17M_{n+1} \qquad \qquad \text{for some integer $M_{n+1} = \cfrac{X_{n+1}}{17}$, as $X_{n+1}$ is a multiple of 17 from above} \\ M_{n+1} &= \cfrac{33^{n+1} - 16^{n+1}}{17} \\ &= \cfrac{33\left(33^n\right) - 16\left(16^n\right)}{17} \\ &= \cfrac{33\left(17M_n + 16^n\right) - 16 \times 16^n}{17} \qquad \qquad \text{as $M_n =\cfrac{X_n}{17} = \cfrac{33^n - 16^n}{17}$} \\ &= \cfrac{17\times 33M_n + 16^n(33 - 16)}{17} \\ &= 33M_n + 16^n \end{align*}$

And, by similar reasoning, $Y_n = 28^n - 11^n = 17N_n$ where $N_{n+1} = 28N_n + 11^n$ .

Note further that $X_1 = 33^1 - 16^1 = 17 = 17M_1 \implies M_1 = 1$ and that $Y_1 = 28^1 - 11^1 = 17 = 17N_1 \implies N_1 = 1$ .

$\textbf{Theorem:} \qquad A_n = X_n - Y_n = 17\left(M_n - N_n\right)\ \text{is divisible by five for all positive integers $n$$
$\text{given $M_{n+1} = 33M_n + 16^n$ and $N_{n+1} = 28N_n + 11^n$ and that $M_1 = N_1 = 1$}$

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

$A_k = 17\left(M_k - N_k\right) = 5P \quad \text{for some positive integer $P$}$

and the working will establish that

$\begin{align*} A_{k+1} &= 17\left(33M_k + 16^k - 28N_k - 11^k\right) \\ &= 17\left[5\times M_k + 28\left(M_k - N_k\right) + 16^k - 11^k\right] \\ &= 17\left(5\times M_k + 28\times 5P + 16^k - 11^k\right) \qquad \qquad \text{after using the induction hypothesis} \\ &= 17\left(5\times M_k + 28\times 5P + 5L\right) \qquad \qquad \text{noting that $16^k - 11^k = 5L$, for some integer $L$, using result (a)} \\ &= 17 \times 5\left(M_k + 28P + L\right) \end{align*}$

NOTES:

As an induction problem, this is too hard to be reasonable as a test of MX2 content.
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.
Splitting $33M_k$ into $28M_k + 5M_k$ in the induction part uses the same idea / approach as is key in @idkkdi's very concise proof above
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 · Sep 19, 2021

CM_Tutor said:
A similar approach...

Result (A)

$\begin{align*} \textbf{Theorem:} \qquad x^n - y^n &= (x - y)\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \quad \text{for positive integers $n$} \\ \\ \textbf{Proof:} \qquad \text{RHS}\ &= (x - y)\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \\ &= x\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) - y\left(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... + y^{n-1}\right) \\ &= x^n + x^{n-1}y + x^{n-2}y^2 + ... + xy^{n-1} - \left(x^{n-1}y + x^{n-2}y^2 + x^{n-3}y^3 + ... + y^n\right) \\ &= x^n + \left(x^{n-1}y - x^{n-1}y\right) + \left(x^{n-2}y^2 - x^{n-2}y^2\right) + ... + \left(xy^{n-1} - xy^{n-1}\right) - y^n \\ &= x^n - y^n \\ &= \text{LHS} \end{align*}$

It follows that $x^n - y^n$ is divisible by $x - y$ for all positive integers $n$ .

Corollaries of Result (A)

$33^n - 16^n$ is divisible by $33-16=17$ .

$28^n - 11^n$ is divisible by $28-11=17$ .

Thus, $33^n - 16^n - 28^n + 11^n = 33^n - 16^n - \left(28^n - 11^n\right)$ is also divisible by 17.

HAHS Proof 1

$33^n - 28^n$ is divisible by $33-28=5$ .

$16^n - 11^n$ is divisible by $16-11=5$ .

Thus, $33^n - 16^n - 28^n + 11^n = 33^n - 28^n - \left(16^n - 11^n\right)$ 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 $17 \times 5 = 85$ .

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 $X_n = 33^n - 16^n$ and $Y_n = 28^n - 11^n$ , I seek that $A_n = X_n - Y_n$ is divisible by 85.

It has been established that $A_n$ is divisible by 17, and that I only need $A_n$ to be divisible by 5.

$\begin{align*} X_{n+1} &= 33^{n+1} - 16^{n+1} \qquad \qquad \text{by definition} \\ &= 17M_{n+1} \qquad \qquad \text{for some integer $M_{n+1} = \cfrac{X_{n+1}}{17}$, as $X_{n+1}$ is a multiple of 17 from above} \\ M_{n+1} &= \cfrac{33^{n+1} - 16^{n+1}}{17} \\ &= \cfrac{33\left(33^n\right) - 16\left(16^n\right)}{17} \\ &= \cfrac{33\left(17M_n + 16^n\right) - 16 \times 16^n}{17} \qquad \qquad \text{as $M_n =\cfrac{X_n}{17} = \cfrac{33^n - 16^n}{17}$} \\ &= \cfrac{17\times 33M_n + 16^n(33 - 16)}{17} \\ &= 33M_n + 16^n \end{align*}$

And, by similar reasoning, $Y_n = 28^n - 11^n = 17N_n$ where $N_{n+1} = 28N_n + 11^n$ .

Note further that $X_1 = 33^1 - 16^1 = 17 = 17M_1 \implies M_1 = 1$ and that $Y_1 = 28^1 - 11^1 = 17 = 17N_1 \implies N_1 = 1$ .

$\textbf{Theorem:} \qquad A_n = X_n - Y_n = 17\left(M_n - N_n\right)\ \text{is divisible by five for all positive integers $n$$
$\text{given $M_{n+1} = 33M_n + 16^n$ and $N_{n+1} = 28N_n + 11^n$ and that $M_1 = N_1 = 1$}$

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

$A_k = 17\left(M_k - N_k\right) = 5P \quad \text{for some positive integer $P$}$

and the working will establish that

$\begin{align*} A_{k+1} &= 17\left(33M_k + 16^k - 28N_k - 11^k\right) \\ &= 17\left[5\times M_k + 28\left(M_k - N_k\right) + 16^k - 11^k\right] \\ &= 17\left(5\times M_k + 28\times 5P + 16^k - 11^k\right) \qquad \qquad \text{after using the induction hypothesis} \\ &= 17\left(5\times M_k + 28\times 5P + 5L\right) \qquad \qquad \text{noting that $16^k - 11^k = 5L$, for some integer $L$, using result (a)} \\ &= 17 \times 5\left(M_k + 28P + L\right) \end{align*}$

NOTES:

As an induction problem, this is too hard to be reasonable as a test of MX2 content.

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.

Splitting $33M_k$ into $28M_k + 5M_k$ in the induction part uses the same idea / approach as is key in @idkkdi's very concise proof above

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.

nvm, was being dumb.

stupid_girl · Sep 19, 2021

mr.habibbi said:
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.

idkkdi · Sep 19, 2021

stupid_girl said:
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 · Sep 19, 2021

Check out James Ruse 2018 Paper. I swear there was something similar!

CM_Tutor · Sep 19, 2021

idkkdi said:
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 $x^n + y^n$ only works for odd $n$ (as then $x^n + y^n = x^n - (-y)^n$ , 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 $n$ is even and the result is certainly true for:

$\begin{align*} \textbf{Take $n = 2$:} \qquad \text{LHS}\ = x^2 - y^2 \qquad \text{RHS}\ &= (x - y)\left(x^{2-1} + x^{2-2}y^1\right) \\ &= (x - y)(x + y) \\ &= x^2 - y^2 \\ &= \text{LHS} \end{align*}$

$\begin{align*} \textbf{Take $n = 4$:} \qquad \text{LHS}\ = x^4 - y^4 \qquad \text{RHS}\ &= (x - y)\left(x^{4-1} + x^{4-2}y^1 + x^{4-3}y^2 + x^{4-4}y^3\right) \\ &= (x - y)\left(x^3 + x^2y + xy^2 + y^3\right) \\ &= x\left(x^3 + x^2y + xy^2 + y^3\right) - y\left(x^3 + x^2y + xy^2 + y^3\right) \\ &= x^4 + x^3y + x^2y^2 + xy^3 - \left(x^3y + x^2y^2 + xy^3 + y^4\right) \\ &= x^4 + \left(x^3y - x^3y\right) + \left(x^2y^2 - x^2y^2\right) + \left(xy^3 - xy^3\right) - y^4 \\ &= x^4 - y^4 \\ &= \text{LHS} \end{align*}$

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

idkkdi · Sep 19, 2021

CM_Tutor said:
Are you sure?

Certainly the factorisation of $x^n + y^n$ only works for odd $n$ (as then $x^n + y^n = x^n - (-y)^n$ , 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 $n$ is even and the result is certainly true for:

$\begin{align*} \textbf{Take $n = 2$:} \qquad \text{LHS}\ = x^2 - y^2 \qquad \text{RHS}\ &= (x - y)\left(x^{2-1} + x^{2-2}y^1\right) \\ &= (x - y)(x + y) \\ &= x^2 - y^2 \\ &= \text{LHS} \end{align*}$

$\begin{align*} \textbf{Take $n = 4$:} \qquad \text{LHS}\ = x^4 - y^4 \qquad \text{RHS}\ &= (x - y)\left(x^{4-1} + x^{4-2}y^1 + x^{4-3}y^2 + x^{4-4}y^3\right) \\ &= (x - y)\left(x^3 + x^2y + xy^2 + y^3\right) \\ &= x\left(x^3 + x^2y + xy^2 + y^3\right) - y\left(x^3 + x^2y + xy^2 + y^3\right) \\ &= x^4 + x^3y + x^2y^2 + xy^3 - \left(x^3y + x^2y^2 + xy^3 + y^4\right) \\ &= x^4 + \left(x^3y - x^3y\right) + \left(x^2y^2 - x^2y^2\right) + \left(xy^3 - xy^3\right) - y^4 \\ &= x^4 - y^4 \\ &= \text{LHS} \end{align*}$

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.

CM_Tutor · Sep 19, 2021

Talia_02 said:
Check out James Ruse 2018 Paper. I swear there was something similar!

Which question do you mean?

induction q (1 Viewer)

notme123

Well-Known Member

idkkdi

Well-Known Member

Life'sHard

Well-Known Member

notme123

Well-Known Member

idkkdi

Well-Known Member

notme123

Well-Known Member

Eagle Mum

Well-Known Member

notme123

Well-Known Member

Eagle Mum

Well-Known Member

CM_Tutor

Moderator

idkkdi

Well-Known Member

stupid_girl

Active Member

idkkdi

Well-Known Member

Talia_02

New Member

CM_Tutor

Moderator

idkkdi

Well-Known Member

CM_Tutor

Moderator

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