My friend gave me a problem:
Prove that if $M_n$ is the $n^\text{th}$ odd number, then for all integers $i$, $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1)\tag*{$[1]$}$$
The following was my attempt at a proof:
Attempt.
Firstly, $(i+n)(i-n)=i^2-n^2$ and $(i+n-1)(i-n+1)=i^2-(n-1)^2$. Note that $$\begin{align}i^2-(n-1)^2&=i^2-(n^2+1-2n^2) \\ &=i^2-n^2+(2n^2-1) \\\therefore M_n &{\;\ }|\,\,\,2n^2-1.\tag*{$\big(\because M_n\mid i^2-n^2\big)$}\end{align}$$
Now since $M_n$ is the $n^\text{th}$ odd number, then $M_n=2n-1$. It thus suffices to prove that $$2n-1\mid 2n^2-1.$$ However, there are cases where $2n^2-1$ is prime, and clearly, $2n-1\neq 2n^2-1$ unless $n\in\{0,1\}$ so I must have done something wrong... however, I didn't think I did, and I thought the question was wrong. So I asked my friend for the proof and he did this:
Proof.
Ignore the case where $n=1$ since that would mean $M_n=1$ and $1$ divides everything.
Suppose that $3\mid i^2-1=(i+1)(i-1)$. Notice that $3\mid i^2-1-3=i^2-4=(i+2)(i-2)$. $$\therefore 3\mid (i+2)(i-2)\Leftrightarrow 3\mid (i+1)(n-1)$$ or $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1).\tag{$n=2$}$$ Suppose that $5\mid i^2-4=(i+2)(i-2)$. Notice that $5\mid i^2-4-5=i^2-9=(i+3)(i-3)$. $$\therefore 5\mid (i+3)(i-3)\Leftrightarrow 5\mid(i+2)(i-2)$$ or $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1).\tag{$n=3$}$$ Suppose that $7\mid i^2-9=(i+3)(i-3)$. Notice that $7\mid i^2-9-7=i^2-16=(i+4)(i-4)$. $$\therefore 7\mid (i+4)(i-4)\Leftrightarrow 7\mid(i+3)(i-3)$$ or $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1).\tag{$n=4$}$$ Clearly, this would continue ad infinitum if (and only if!) $$\sum_{j=1}^k (2j-1)=k^2\tag{for some $k$}$$ which is a well-known theorem. Since this is true, then $[1]$ therefore deems true. $\;\bigcirc$
His proof looks correct, I don't doubt... but what is wrong with my own attempt? It's late for me now, as well as my friend, so he went to bed, and unfortunately he didn't have the time to tell me.
Hence, I didn't go to bed, and I came to the MSE!
May someone please tell me where my mistake is in my attempt of the proof? I cannot find it, and surely there must be at least one... right?
Thank you in advance.
Answer
Your mistake is that $(n-1)^2=n^2-2n+1$, but you write
$$(n-1)^2=n^2-2n^2+1.$$
You get stuck trying to prove that $2n-1\mid 2n^2-1$, which indeed fails for some $n$, when in fact this should be $2n-1\mid2n-1$, which is obviously true.
Of course, this does not yet prove that $M_n$ divides both
$$(i-n)(i+n)\qquad\text{ and }\qquad(i-n+1)(i+n-1),$$
but only that $M_n$ divides their difference. You will have a hard time proving the statement however, because it is false (as noted in the comment below). This is illustrated very clearly by taking $i=0$; it is clear that $2n-1$ divides $-n^2$ if and only if $n=1$ (or $n=0$ if that is allowed).
No comments:
Post a Comment