1

Let $P_n$ be a proposition, so that $$P_n: 3+11+...+(8n-5)=4n^2-n$$ $P_1:3=4\cdot1^2-1$, $P_2:3+11=4\cdot2^2-2$ etc.

When proving $P_n\to P_{n+1}$, is it enough to show in the second induction step that, by subtracting from both sides we have $$4(n+1)^2-(n+1)=4n^2-n+(8(n+1)-5)\leftrightarrow0=0$$ and therefore $P_n\to P_{n+1}$. Or do I must rewrite $4n^2-n+(8(n+1)-5)$ to $4(n+1)^2-(n+1)$?

mechanicious
  • 413
  • 3
  • 13
  • The second way is more elegant. – Bernard Jun 09 '18 at 20:53
  • 1
    I think it is valid, but I would prefer to start with $n=1$ to avoid the argument with the empty sum. – Peter Jun 09 '18 at 20:53
  • @Peter Yes, I would normally start with n=1. I have not mentioned it, but the induction in the content of the question doesn't aim to be complete. The question is just about a little part of the proof. – mechanicious Jun 09 '18 at 20:55
  • @Bernard Yeah, right? I also think so, but sometimes it's not practical. I am only concerned about the validity of the proof. – mechanicious Jun 09 '18 at 21:02
  • Yet the second way is easy: rewrite $4n^2-n+8(n+1)-5$ as $4n^2+8n +3-n=(4n^2+8n +4)-(n+1)$. – Bernard Jun 09 '18 at 21:10
  • 1
    No. Proving $0 = 0$ doesn't prove anything. It just proves that you didn't succeed in disproving something. If I wanted to prove Elephants and horses were the same animal, I'd say the average number of pounds of salmon each eat in a year would be the same. And that number for both of them is $0$. Therefore elephants and horses are the same animal. – fleablood Jun 09 '18 at 21:31
  • If you don't know that the are equal you can't $f(n) = g(n)$ so $4(n+1)^2-(n+1)=4n^2-n+(8(n+1)-5)$ so $0 = 0$. What you have to say instead is $f(n) = 4(n+1)^2-(n+1)=$ and $g(n) = 4n^2-n+(8(n+1)-5)$. And those to terms are equal... OR you have to specify every step is an if and only if reasoning and works both ways. If you have logical inferences that work only one way, then you can only prove in that direction. – fleablood Jun 09 '18 at 21:35
  • @fleablood I am not proving $0=0$ I am just using it to make clear that both sides of the equation are equivalent... – mechanicious Jun 09 '18 at 21:36
  • 1
    You must do that the correct way. And $a = b \to k = j \to 0= 0$ is the wrong way. The correct way is either $a=k = j = b$ or $a=b \iff k = j \iff 0=0$. The $\iff$ is ESSENTIAL. Sorry, but I am a real hard-ass on that account. – fleablood Jun 09 '18 at 21:38
  • In other words $4(n+1)^2-(n+1)=4n^2-n+(8(n+1)-5)\to0=0$ is not okay but $4(n+1)^2-(n+1)=4n^2-n+(8(n+1)-5)\leftrightarrow 0=0$ is. – fleablood Jun 09 '18 at 21:39
  • @fleablood Yeah, I get it. You're right on that. But $a\to b$ does not necessarily mean $a\nLeftarrow b$ does it? – mechanicious Jun 09 '18 at 21:42
  • It must certainly does not which is why you absolutely MUST specify $\iff$. Otherwise all you have proven is "If we assume what we want to prove we get something that is true". What you want to do instead is "If we assume what we want to prove we get through a series of equivalent statements something that is true". That is enough because you are proving $\iff$. Not just $\implies$. – fleablood Jun 09 '18 at 21:56
  • If you start by stating what needs to be proven then all your statements must be $\Leftarrow$ ("is implied by"). $\implies$ ("implies") are totally useless (because you are starting with what supposed to be proven and you don't know if it is true... and you end with what always know was true anyway). Now it might be clear to you that you are doing $\iff$ statements which include both $\implies$ and $\Leftarrow$. But you must say so. Otherwise it is assumed you are only doing the $\implies$. Which just won't work. – fleablood Jun 09 '18 at 22:00
  • @fleablood That's right I want to show that $0=0\to a=b$ not only that $a=b\to0=0$. Basically, $a=b\to0=0$ is there only to make it clearer to see that $0=0\to a=b$. I have corrected my question. – mechanicious Jun 09 '18 at 22:09
  • @fleablood Btw. if I rewrite $a=b$ to $0=0$ using proven identities, doesn't it mean that I've got $a=b\to0=0$ which is equivalent to $(X\to T)\to T$ hence $X$ must be a true value? – mechanicious Jun 09 '18 at 22:15
  • No. Because $(F\to T)\to T$ is also true. $X\to T$ is always true. And that is exactly why this doesn't work. ( (Elephants are Horses)$\to$ Elephants eat the same amount of salmon) $\to 0 = 0$ is valid and true. – fleablood Jun 09 '18 at 22:19
  • @fleablood Nvm. $(F\to T)\leftrightarrow T$ per definition. – mechanicious Jun 09 '18 at 22:19
  • And YES that is TRUE and THAT works. So $(X\leftarrow T)\leftarrow T$ DOES mean $X$ is true. – fleablood Jun 09 '18 at 22:20
  • Sorry, I am a hard ass. But it's a common novice problem to mangle proofs this way. And frequently the do make an error. You wouldn't, but many do try to do things like if ... blah... blah blah ... then prove $x + y = 5$ with. $x + y = 5 \to (x+y)^2 = 25 \to...\to 0= 0$ which is of course wrong. So I do drop down like a ton of bricks on this. Sorry. – fleablood Jun 09 '18 at 22:28
  • @fleablood I think that it is great that you do that. It has corrected my error. Keep on dropping bricks on it ;>! – mechanicious Jun 09 '18 at 22:31

1 Answers1

1

I would rather make the use of induction extremely clear.

First of all, I would write $P_n: 3+11+...+(8n-5)=4n^2-n $ as $P_n: \sum_{k=1}^n (8n-5) =4n^2-n $. This makes the start and end terms of the sum clear and reduces the chance of error.

Then I would show the step from $P_n$ to $P_{n+1}$ like this:

$\begin{array}\\ \sum_{k=1}^{n+1} (8n-5) &=\sum_{k=1}^{n} (8n-5)+8(n+1)-5 \qquad\text{split off the last term}\\ &=4n^2-n+8(n+1)-5 \qquad\text{use the induction hypothesis}\\ &=4n^2+7n+3 \qquad\text{algebra}\\ &=4(n+1)^2-(n+1) \qquad\text{more algebra to get the right side of }P_{n+1}\\ \end{array} $

which is $P_{n+1}$, and we are done.

More generally, suppose we are given $a$ and $b$, and we want to find $u, v, $ and $w$ such that $P_n: \sum_{k=1}^n (an+b) =un^2+vn+w $ is true.

Arguing exactly as above,

$\begin{array}\\ \sum_{k=1}^{n+1} (an+b) &=\sum_{k=1}^{n} (an+b)+a(n+1)+b \qquad\text{split off the last term}\\ &=un^2+vn+w+a(n+1)+b \qquad\text{use the induction hypothesis}\\ &=un^2+(v+a)n+w+a+b \qquad\text{algebra}\\ \end{array} $

$P_{n+1}$ is $\sum_{k=1}^{n+1} (an+b) =u(n+1)^2+v(n+1)+w $, so we want

$un^2+(v+a)n+w+a+b\\ =u(n+1)^2+v(n+1)+w\\ =un^2+(2u+v)n+u+v+w. $

Equating coefficients, $v+a = 2u+v$ and $w+a+b = u+v+w$.

From the first, $u = a/2$.

From the second, $a+b = u+v =a/2+v$ so $v = a/2+b$.

For your problem, $a=8, b=-5$, so $u = 4, v=8/2-5 =-1 $.

Note that $w$ does not seem to be determined. For this, we need the initial value; either $n=0$ or $n=1$ will work.

Using $n=0$, the sum is empty, so we want $0 = w$.

Using $k=1$, $P_1$ is $a+b = u+v+w$ or $w =a+b-u-v =a+b-a/2-(a/2+b) = 0 $.

It is comforting that both cases lead to the same result.

Therefore we have shown that $\sum_{k=1}^n (ak+b) =(a/2)n^2+(a/2+b)n $.

This type of argument enables us to both discover a result and prove it.

In some problems, this technique allows us to show that a particular form of a summation does not exist, because the assumption that the form exists leads to a contradiction.

marty cohen
  • 107,799
  • +1 for making the induction step very clear. But alternatively one can proceed as follows: assume that $P_n$ is true then substitute $n+1$ for $n$ in the equation of $P_n$. Since that equation must be true, and since it is equivalent to the equation in the proposition of $P_{n+1}$ we have that $P_n\to P_{n+1}$. Which is what I am using. – mechanicious Jun 09 '18 at 21:53
  • In all cases, it is equivalent to showing that $4n^2-n + (8(n+1)-5) = 4(n+1)^2-(n+1)$. – marty cohen Jun 09 '18 at 22:08