9
$\begingroup$

My problem is I keep ending up proving the statement true, instead of disproving it. I was getting it mixed up in my mind so I broke it down into very explicit steps but now I'm wondering if I'm overthinking it?

I started out proving that if there is no integer solution, then k is even (one negation of the statement, $P$ and not $Q$ where $P = \text{ no integer solution and } Q = k \text{ is odd}$). By contrapositive I try to prove that if $k$ is odd then there is an integer solution (I quickly recognized this is the same as the other negation, $Q$ and not $P$, so this is the only thing I need to prove).

So $k = 2n + 1$ for any integer $n$. Then $x^2-x -(2n+1) = 0$. So $x^2-x=2n+1$. But if $x$ is an integer then $x^2-x$ must always be even, and cannot equal an odd integer $2n+1$. So this has led to a contradiction, which means I just proved that if k is odd then there is no integer solution.

Is my logic off somewhere, or should I be approaching it differently? Sorry if this has an obvious answer, I only started doing proofs this quarter. Thanks

$\endgroup$
  • $\begingroup$ You proved in the end that ($k$ is odd) $\implies$ (no integer solutions). Now you still have to prove the sufficient condition and that is if there is (no integer solutions) $\implies$ ($k$ is odd), which is equivalent to proving ($k$ is not odd) $\implies$ (there exist an integer solution). I think you didn't prove this, am I right? $\endgroup$ – Fareed Abi Farraj Jan 23 at 7:34
  • $\begingroup$ If k is negative (say -2) then there are clearly no real solutions at all as x^2-x is never smaller than -1/4. $\endgroup$ – RemcoGerlich Jan 23 at 10:58
13
$\begingroup$

You seem to be struggling with the logic involved here. The statement is $$ k\text{ is odd}\iff x^2-x-k=0\text{ has no integer solutions} $$ Yes, it seems that making $k$ odd makes the equation have no integer solutions (in other words, the $\implies$ direction is true). Your proof of this looks fine.

However, the statement also claims that if there are no integer solutions, then $k$ is odd (the $\Longleftarrow$ direction). The contrapositive of this claim is that making $k$ even will always result in an integer solution. This is disproven by providing a single counterexample.

$\endgroup$
7
$\begingroup$

Hint:

$x^2-x-k=0 \Rightarrow x=\frac{1 \pm \sqrt{4k+1}}{2}$

So $x$ can only be an integer if $4k+1$ is the square of an odd number.

This is true when $k=2$, in which case $\sqrt{4k+1}=3$, and when $k=6$, in which case $\sqrt{4k+1}=5$.

But what about when $k=4$ ?

$\endgroup$
4
$\begingroup$

Lets assume that equation has integer solutions, so $ x \in Z $

$x^2-x = k$

$x (x-1) = k$

$x-1$ and $x$ are two consecutive integer numbers, their product is even $\Rightarrow k$ is even

$\endgroup$
  • 1
    $\begingroup$ I like this approach. What would make it complete is a quick listing of products of consecutive integers: $2\cdot 3=6,\ 3\cdot 4=12,\ 4\cdot 5=20$ etc. That would illustrate that there are many even values of $k$ ($8,10,14, 16,18,\dots$) that are not solutions. It is necessary that $k$ be even, but not sufficient for the equation to have integer solutions. $\endgroup$ – Keith Backman Jan 23 at 18:03

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.