1
$\begingroup$

Problem: Prove that for any positive integer k, there exist k consecutive positive integers that are not perfect squares.

Proof: Consider the positive integers $k$ and $k+1$.

$(k+1)^2 - k^2 = 2k+1 \geq k$.

Thus, there are at least $k$ consecutive positive integers that are not perfect squares between $k$ and $k+1$.

Is this a non-constructive proof because I have not defined the $k$ consecutive positive integers? Would the following be a constructive proof?

Proof: Consider the set of $k$ consecutive positive integers $S=\{k^2+1, k^2+2, ..., k^2+k\}$.

Since the next perfect square after $k^2$ is $(k+1)^2=k^2+2k+1>k^2+k$, the set $S$ is a set of non-perfect squares with cardinality $k$.

$\endgroup$
5
  • $\begingroup$ I think both of the proofs are the same, you just explicitly gave the numbers which are not squares in the second one, but you still constructed them in the first proof, it is just a matter of how precise you get. Your first proof gives a way of finding the squares so in this way it is constructive. $\endgroup$
    – Junkyards
    Commented Jan 27, 2019 at 23:18
  • $\begingroup$ I see, so since the numbers are implicitly defined it is a constructive proof. $\endgroup$
    – Pareod
    Commented Jan 27, 2019 at 23:20
  • 1
    $\begingroup$ Kind of, I would say really that what matters to say if a proof is constructive or not is if the proof gives anyone a way to actually write down the elements you show the existence of. An example of a non constructive proof is any (classical?) proof of the intermediate value theorem : it just cannot say which element is a zero of the function $\endgroup$
    – Junkyards
    Commented Jan 27, 2019 at 23:24
  • $\begingroup$ Okay, thanks. I understand it mor clearly now. $\endgroup$
    – Pareod
    Commented Jan 27, 2019 at 23:49
  • $\begingroup$ In the first proof it should say there are $k$ consecutive nonsquare numbers between $k^2$ and $(k+1)^2$ $\endgroup$
    – Ross Millikan
    Commented Jan 28, 2019 at 0:13

1 Answer 1

Reset to default
1
$\begingroup$

I would call both your proofs constructive because you give a particular series of $k$ sequential nonsquare numbers. A nonconstructive proof would show that somewhere there is a sequence of $k$ nonsquare numbers, but would give no idea of how large even the first such sequence must be. One approach would be to assume there is no sequence of $k$ nonsquare numbers and reach a contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .