1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ Btw $i=7$ and $n=5$ doesn't work $\endgroup$ – TheSimpliFire Mar 30 at 12:29
  • $\begingroup$ Yeah, I had a chat with @TheSimpliFire about it; $[1]$ is not true for all integers $i$ anyways, so... yeah. I will tell this to my friend tomorrow >:| but thanks for the answer. Just a small quick thing, but: what do you mean by the first part of your answer? Where exactly have I demonstrated that $(n-1)^2=n^2-2\color{red}{n}+1$? $\endgroup$ – Mr Pie Mar 30 at 12:39
  • 1
    $\begingroup$ @user477343 In your attempt you write that $$\begin{align} i^2-(n-1)^2 &=i^2-(n^2+1-2n^2) \\ &=i^2-n^2+(2n^2-1) \end{align},$$ but in both lines the $2n^2$ term should be $2n$. $\endgroup$ – Servaes Mar 30 at 14:14
  • $\begingroup$ Oh, wait, I thought... ok, I see. Thanks for that. I will give you a tick for focusing on this :) $\color{green}{\checkmark}$ $\endgroup$ – Mr Pie Mar 30 at 22:16
1
$\begingroup$

Your friend actually did nothing, but your evaluation is incorrect as well.

Indeed, $M_n|(i+n)(i-n)$ is equivalent to $M_n|(i+n-1)(i-n+1)$.

But you realize this actually says nothing.

I am curious what your friend was trying to show there.

If it is induction, it would be the worst induction I have ever seen.

You see the statement is about $i$, not $n$, so what you should use induction on $i$, that is , if$M_n|(i+n)(i-n)$, then $M_n|(i+1+n)(i+1-n)$( the "and" statement, as shown, is equal to this one), which leads to $2n-1|2i+1$, is a nosense

And your friend doesn not show his base case. The base case should be $2n-1|n^2-1$, which is another nonsense, just pick $2n-1$ as any prime number.

There is nothing valid here, he just used a very very bad inudction, that is all.

$\endgroup$
  • $\begingroup$ $(+1)$: yep, I totally agree. Too bad it's $11$:$44$pm here where I am, so my friend is in bed now, probably dreaming about this... before I let him know of his atrocious mistakes tomorrow. $\endgroup$ – Mr Pie Mar 30 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.