Challenging (?) Proof Question (1 Viewer)

CM_Tutor · Apr 2, 2020

Prove that if $M \notin \mathbb{Z}$ but $M + \cfrac{1}{M} = \cfrac{M^2 + 1}{M} \in \mathbb{Z}$ , then $M^n + \cfrac{1}{M^n} \in \mathbb{Z}$ for all $n \in \mathbb{Z}^+$ .

I am curious as to how Extension 2 students would approach this as a proof problem, and wondering if there are other approaches beyond the two that occur to me.

fan96 · Apr 2, 2020

Is the condition $M \notin \mathbb Z$ really necessary?

The only case of this I can see is $1 + 1/1 = 2 \in \mathbb Z$ , so it would be simpler to leave it unmentioned.

ultra908 · Apr 2, 2020

u can prove by strong induction, n=0 is obvs true, given n=1, then $M^{k + 1} + \cfrac{1}{M^{k + 1}} = (M^k + \cfrac{1}{M^k})(M + \cfrac{1}{M}) - (M^{k - 1} + \cfrac{1}{M^{k - 1}})$ is integer

fan96 · Apr 2, 2020

If one wanted to actually find examples of $M$ , here is an approach that works for $M \in \mathbb R$ .

I'll use the hyperbolic function $\cosh$ and its inverse, which aren't in the MX2 syllabus but their definitions are quite simple to understand:

$\cosh x = \frac 12 \left(e^x+e^{-x}\right)$ and $\cosh x = y \implies y = \log(x\pm\sqrt{x^2-1})$

Now, let

$f(x) = x^n + \frac 1{x^n}$ ,

be a real function where $n \in \mathbb Z$ .

If $n$ is even, then $f(x) = f(-x)$ .
If $n$ is odd, then $f(x)=-f(-x)$ .
That is, the parity of $f$ is the parity of $n$ .

So without loss of generality, assume $M > 0, \, n > 0$ and make the substitution $M = e^x$ .

If $f(M) = k$ for some $k \in \mathbb Z$ , then

$e^{nx}+e^{-nx} = k$ , so

$\cosh (nx) = \frac k2,$

$nx = \log\left(\frac k2 \pm \sqrt{\frac {k^2}4 - 1}\right).$

Since $x = \log M$ ,

$M^n = \frac k2 \pm \sqrt{\frac {k^2}4 - 1}$ .

We require $|k| \ge 2$ , which should be expected, as $y + (1/y) \ge 2$ for all positive $y$ .

The original proposition

$M + \frac 1M \in \mathbb Z \implies M^n + \frac 1{M^n} \in \mathbb Z$

is equivalent (I believe) to

$2 \cosh(x) \in \mathbb Z \implies 2 \cosh(nx) \in \mathbb Z$ .

We also find an interesting identity:

$\frac x2 \pm \sqrt{\frac {x^2}4 - 1} + \frac{1}{\frac x2 \pm \sqrt{\frac {x^2}4 - 1}} \equiv x$

for all $|x| \ge 2$ .

EDIT: It's worth noting that this shows that if $M \in \mathbb Z$ , then $k = \pm 2$ .
If $M^n = 1/2(k \pm \sqrt{k^2 - 4})$ then $\sqrt{k^2 - 4} \in \mathbb Z$ .
The gap between the second and third perfect square is $3^2-2^2 = 5 > 4$ , and this gap will only increase as you go further out.
So $k^2 \le 2^2 \implies k = \pm 2$ . Subbing in these values confirms that $M^n = \pm 1 \implies M = \pm 1$ .

ewjfiwhelowaeoplg · Apr 2, 2020

Yes, strong induction is the standard X2 approach for these sorts of questions

CM_Tutor · Apr 3, 2020

fan96 said:
Is the condition $M \notin \mathbb Z$ really necessary?

The only case of this I can see is $1 + 1/1 = 2 \in \mathbb Z$ , so it would be simpler to leave it unmentioned.

There is one other possibility, $M = -1$ , so I take your point that requiring $M \notin \mathbb{Z}$ isn't really necessary... but it does open the opportunity to expand the proof question to ask for all possible solutions if M is an integer, including a proof that there are no other possibilities with $M \in \mathbb{Z}$ .

On reflection, the result is also true if the restriction on n is simply $n \in \mathbb{Z}$

CM_Tutor · Apr 3, 2020

I agree that the induction approach noted by ultra908 is the obvious / standard approach. The approach from fan96 is not one I had considered, but it's also beyond the MX2 syllabus. Are there any other approaches anyone would consider?

HeroWise · Apr 4, 2020

Use Binomials to expand (M+1/M)^n?

5uMath · Apr 4, 2020

CM_Tutor said:
Prove that if $M \notin \mathbb{Z}$ but $M + \cfrac{1}{M} = \cfrac{M^2 + 1}{M} \in \mathbb{Z}$ , then $M^n + \cfrac{1}{M^n} \in \mathbb{Z}$ for all $n \in \mathbb{Z}^+$ .

I am curious as to how Extension 2 students would approach this as a proof problem, and wondering if there are other approaches beyond the two that occur to me.

You could go into complex numbers and use Taylor series expressions for real and imaginary part, then you could prove local finite integer ABSOLUTE convergence from a point, calling z_n = M^n + M^(-n) and by proving that |Re(z_n)| and |Im(z_n)| ==> |z_n| converges. Type of approach from complex analysis.

HeroWise · Apr 5, 2020

Does my Binomial expansion not work, cus that and Induction is the only way My small brain can think off. was thinking of complex numbers too since its in that form but yeah haha

CM_Tutor · Apr 5, 2020

HeroWise said:
Does my Binomial expansion not work, cus that and Induction is the only way My small brain can think off. was thinking of complex numbers too since its in that form but yeah haha

Yes, it will work, but it is effectively a strong induction proof:

$\Bigg(M + \cfrac{1}{M}\bigg)^n = \binom{n}{0} M^n \Bigg(\cfrac{1}{M}\Bigg)^0 + \binom{n}{1} M^{n - 1} \Bigg(\cfrac{1}{M}\Bigg)^1 + \binom{n}{2} M^{n - 2} \Bigg(\cfrac{1}{M}\Bigg)^2 + \binom{n}{3} M^{n - 3} \Bigg(\cfrac{1}{M}\Bigg)^3 + ... + \binom{n}{n - 1} M^{n - (n - 1)} \Bigg(\cfrac{1}{M}\Bigg)^{n - 1} + \binom{n}{n} M^{n - n} \Bigg(\cfrac{1}{M}\Bigg)^n$
$= \binom{n}{0} M^n + \binom{n}{1} M^{n - 2} + \binom{n}{2} M^{n - 4} + \binom{n}{3} M^{n - 6} + ... + \binom{n}{n - 2} \cfrac{1}{M^{n - 4}} + \binom{n}{n - 1} \cfrac{1}{M^{n - 2}} + \binom{n}{n} \cfrac{1}{M^n}$

Now, applying the symmetry property that $\binom{n}{r} = \binom{n}{n - r}$

$= \binom{n}{0} M^n + \binom{n}{1} M^{n - 2} + \binom{n}{2} M^{n - 4} + \binom{n}{3} M^{n - 6} + ... + \binom{n}{2} \cfrac{1}{M^{n - 4}} + \binom{n}{1} \cfrac{1}{M^{n - 2}} + \binom{n}{0} \cfrac{1}{M^n}$
$= \binom{n}{0} \Bigg(M^n + \cfrac{1}{M^n}\Bigg) + \binom{n}{1} \Bigg(M^{n - 2} + \cfrac{1}{M^{n - 2}}\Bigg) + \binom{n}{2} \Bigg(M^{n - 4} + \cfrac{1}{M^{n - 4}}\Bigg) + ...$

Now, the last term in this series of sums depends on whether $n$ is odd or even, so it is best rewritten as:

$\underline{\text{Case 1:}} \quad \text{Put } n = 2m\text{:}$
$\Bigg(M + \cfrac{1}{M}\bigg)^{2m} = \binom{2m}{0} \Bigg(M^{2m} + \cfrac{1}{M^{2m}}\Bigg) + \binom{2m}{1} \Bigg(M^{2m - 2} + \cfrac{1}{M^{2m - 2}}\Bigg) + \binom{2m}{2} \Bigg(M^{2n - 4} + \cfrac{1}{M^{2n - 4}}\Bigg) + ... + \binom{2m}{m - 1}} \Bigg(M^2+ \cfrac{1}{M^2}\Bigg) + \binom{2m}{m}$

$\underline{\text{Case 2:}} \quad \text{Put } n = 2m + 1\text{:}$
$\Bigg(M + \cfrac{1}{M}\bigg)^{2m + 1} = \binom{2m + 1}{0} \Bigg(M^{2m + 1} + \cfrac{1}{M^{2m + 1}}\Bigg) + \binom{2m + 1}{1} \Bigg(M^{2m - 1} + \cfrac{1}{M^{2m - 1}}\Bigg) + \binom{2m + 1}{2} \Bigg(M^{2m - 3} + \cfrac{1}{M^{2m - 3}}\Bigg) + ... + \binom{2m + 1}{m - 1} \Bigg(M^3+ \cfrac{1}{M^3}\Bigg) + \binom{2m + 1}{m} \Bigg(M + \cfrac{1}{M}\Bigg)$

Whether $n$ is odd or even, we can see that $M^n + \cfrac{1}{M^n}$ can be rewritten as $\Bigg(M + \cfrac{1}{m}\Bigg)^n$ , which must be an integer, and a series of terms each which has a binomial coefficient (an integer) and an expression $M^k + \cfrac{1}{M^k}$ for some integer $k < n$ . Thus, so long as $M + \cfrac{1}{M}$ is an integer and we do strong induction (where we assume that the result is true for all $n \in \{1, 2, 3, ..., k\}$ and then prove it follows that it must be true for $n = k + 1$ ), we can get the required result for all $n \in \mathbb{Z}^+$

CM_Tutor · Apr 5, 2020

I was thinking about a proof like this: The quadratic equation with roots at $x = M \text{ and } x = M^{-1}$ is

$\big(x - M\big)\big(x - M^{-1}\big) = 0$ , which expands and rearranges to give $x^2 = \big(M + M^{-1}\big)x - 1$

It follows that $x^2 = C_2 x + D_2 \text{ where } C_2 = M + M^{-1} \text{ and } D_2 = -1... \text{, and so } C_2, D_2 \in \mathbb{Z}.$

We then prove that $x^n = C_n x + D_n \text{ where } C_n, D_n \in \mathbb{Z}$ , with or without using induction,

because that gives $M^n + M^{-n} = C_2 C_n + 2D_n$ must be an integer.

Paradoxica · Apr 5, 2020

CM_Tutor said:
I was thinking about a proof like this: The quadratic equation with roots at $x = M \text{ and } x = M^{-1}$ is

$\big(x - M\big)\big(x - M^{-1}\big) = 0$ , which expands and rearranges to give $x^2 = \big(M + M^{-1}\big)x - 1$

It follows that $x^2 = C_2 x + D_2 \text{ where } C_2 = M + M^{-1} \text{ and } D_2 = -1... \text{, and so } C_2, D_2 \in \mathbb{Z}.$

We then prove that $x^n = C_n x + D_n \text{ where } C_n, D_n \in \mathbb{Z}$ , with or without using induction,

because that gives $M^n + M^{-n} = C_2 C_n + 2D_n$ must be an integer.

This is completely valid but technically requires induction to complete the argument for all naturals.

CM_Tutor · Apr 5, 2020

Paradoxica said:
This is completely valid but technically requires induction to complete the argument for all naturals.

The logic is inductive, I agree, though it doesn't actually need to be presented as an induction proof.

Challenging (?) Proof Question (1 Viewer)

CM_Tutor

Moderator

fan96

617 pages

ultra908

Active Member

fan96

617 pages

ewjfiwhelowaeoplg

New Member

CM_Tutor

Moderator

CM_Tutor

Moderator

HeroWise

Active Member

5uMath

Member

HeroWise

Active Member

CM_Tutor

Moderator

CM_Tutor

Moderator

Paradoxica

-insert title here-

CM_Tutor

Moderator

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