# Challenging (?) Proof Question (1 Viewer)

#### CM_Tutor

##### Well-Known Member
Prove that if $\bg_white M \notin \mathbb{Z}$ but $\bg_white M + \cfrac{1}{M} = \cfrac{M^2 + 1}{M} \in \mathbb{Z}$, then $\bg_white M^n + \cfrac{1}{M^n} \in \mathbb{Z}$ for all $\bg_white 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

##### 617 pages
Is the condition $\bg_white M \notin \mathbb Z$ really necessary?

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

#### ultra908

##### Active Member
u can prove by strong induction, n=0 is obvs true, given n=1, then $\bg_white 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

Last edited:

#### fan96

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

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

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

Now, let

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

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

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

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

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

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

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

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

Since $\bg_white x = \log M$,

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

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

The original proposition

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

is equivalent (I believe) to

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

We also find an interesting identity:

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

for all $\bg_white |x| \ge 2$.

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

Last edited:

#### ewjfiwhelowaeoplg

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

#### CM_Tutor

##### Well-Known Member
Is the condition $\bg_white M \notin \mathbb Z$ really necessary?

The only case of this I can see is $\bg_white 1 + 1/1 = 2 \in \mathbb Z$, so it would be simpler to leave it unmentioned.
There is one other possibility, $\bg_white M = -1$, so I take your point that requiring $\bg_white 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 $\bg_white M \in \mathbb{Z}$.

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

#### CM_Tutor

##### Well-Known Member
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

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

#### 5uMath

##### Member
Prove that if $\bg_white M \notin \mathbb{Z}$ but $\bg_white M + \cfrac{1}{M} = \cfrac{M^2 + 1}{M} \in \mathbb{Z}$, then $\bg_white M^n + \cfrac{1}{M^n} \in \mathbb{Z}$ for all $\bg_white 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

##### Active Member
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

##### Well-Known Member
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:

$\bg_white \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$
$\bg_white = \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 $\bg_white \binom{n}{r} = \binom{n}{n - r}$

$\bg_white = \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}$
$\bg_white = \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 $\bg_white n$ is odd or even, so it is best rewritten as:

$\bg_white \underline{\text{Case 1:}} \quad \text{Put } n = 2m\text{:}$
$\bg_white \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}$

$\bg_white \underline{\text{Case 2:}} \quad \text{Put } n = 2m + 1\text{:}$
$\bg_white \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 $\bg_white n$ is odd or even, we can see that $\bg_white M^n + \cfrac{1}{M^n}$ can be rewritten as $\bg_white \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 $\bg_white M^k + \cfrac{1}{M^k}$ for some integer $\bg_white k < n$. Thus, so long as $\bg_white M + \cfrac{1}{M}$ is an integer and we do strong induction (where we assume that the result is true for all $\bg_white n \in \{1, 2, 3, ..., k\}$ and then prove it follows that it must be true for $\bg_white n = k + 1$), we can get the required result for all $\bg_white n \in \mathbb{Z}^+$

#### CM_Tutor

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

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

It follows that $\bg_white 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 $\bg_white x^n = C_n x + D_n \text{ where } C_n, D_n \in \mathbb{Z}$, with or without using induction,

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

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

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

It follows that $\bg_white 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 $\bg_white x^n = C_n x + D_n \text{ where } C_n, D_n \in \mathbb{Z}$, with or without using induction,

because that gives $\bg_white 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

##### Well-Known Member
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.