3
$\begingroup$

I understand that most people use the inductive hypothesis, but I find that counterintuitive. Is the below proof correct? In particular, I am concerned with my use of $n$ in (I); is the reason people use another variable, e.g. $k$, for conceptual reasons, or does the use of $n$ create an error in my proof?

\begin{align*} P(0) \land [P(k) \Rightarrow P(k+1)] \implies P(n) \tag{AI} \\ \end{align*}


\begin{align*} \text{When }n = 2, \ \ 2 + 6 + 10 + . . . + (4n - 2) &= 2n^2 \tag{B} \\ 2 + 6 &= 2 \cdot 2^2 \\ 8 &= 8 \\ \end{align*}


$$ \begin{pmatrix} 2 + 6 + 10 + ... + (4n-2) = 2n^2 \\ \Big\Downarrow \\ 2 + 6 + 10 + ... + (4n-2) + (4(n+1)-2) = 2(n+1)^2 \\ \end{pmatrix} \tag{I} $$ \begin{align*} \Big\Updownarrow \end{align*} \begin{align*} 4(n+1)-2 &= 2(n+1)^2 -2n^2 \\ 4n+4-2 &= 2n^2+4n+2 - 2n^2 \\ 4n+2 &= 4n+2 \\ \end{align*}


$$ \text{B} \land \text{I} \land \text{AI} \implies 2 + 6 + 10 + . . . + (4n - 2) = 2n^2 \text{ for } n > 1 \ \ \square $$


Is this alternate solution correct? I am confident in my reasoning, but am unsure if it is a valid mathematical argument.

Pairing $1$st with $n$th term, $2$nd with $(n-1)$th term, etc., yields $\mathbf{\frac{n}{2}}$ pairs: \begin{align*} 2 + (4n-2) \ \ + \ \ 6 + (4(n-1)-2) \ \ + \ \ 10 + (4(n-2)-2) \ \ + \ \ ... &= 2n^2 \\ 2 + (4n-2) \ \ + \ \ 6 + (4n-6) \ \ + \ \ 10 + (4n-10) \ \ + \ \ ... &= 2n^2 \\ 4n \ \ + \ \ 4n \ \ + \ \ 4n \ \ + \ \ ... &= 2n^2 \\ 4n \cdot \mathbf{\frac{n}{2}} &= 2n^2 \\ 2n^2 &= 2n^2 \\ &\ \square \\\ \\ \end{align*}

$\endgroup$
  • $\begingroup$ Yes, your proof seems fine to me, but it would be much quicker to use the identity for $n^2$. $\endgroup$ – Shaun Sep 28 '17 at 12:52
  • 1
    $\begingroup$ @Shaun: You mean $n^2 = 1 + 3 + 5 + ... + 2n-1$? How do you prove that without induction? $\endgroup$ – Zaz Sep 28 '17 at 12:55
  • $\begingroup$ Yes. I don't know, @Zaz; that's a separate question. $\endgroup$ – Shaun Sep 28 '17 at 12:56
  • $\begingroup$ Here 's a [Proof without induction][1] of that sum (see answer section). [1]: math.stackexchange.com/questions/1666075/… $\endgroup$ – Wyllich Sep 28 '17 at 13:04
  • $\begingroup$ Your method is a special case of telescopic induction, e.g. see this answer. $\endgroup$ – Bill Dubuque Sep 28 '17 at 14:16
1
$\begingroup$

The first proof is perfectly fine. The choice of letters is mostly/often just for aestetical/pedagogical reasons.

The second (and to some extent the first) uses the $\dots$ informal notation. This should probably be seen as a shorthand or more visual way of handling summations. Formally one should have used $\sum$-notation. The problem in the last is that you visually rearranges the terms which is not that good looking when using $\sum$ notation.

The second approach if done strictly would also need induction to be complete (unless you rely on propositions that already have been proven by induction).

$\endgroup$

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.