0

When we do proof by induction our inductive step is to assume that the statement $P(n)$ holds for $n=k$, we then show that $P(k) \implies P(k+1)$, which my textbook writes as "If its true for $n=k$, show its true for $n=k+1$", now I would like to ask this question, why are we allowed to write both $n=k$ and $n=k+1$ without it implying $k=k+1$? Sorry if this question is trivial/not appropriate for stackexchange. Also can we say that $P(n)$ is defined for all $n \geq 0$, but not necessarily true?

Nav Bhatthal
  • 1,057
  • "n=k" and "n=k+1" are not satisfied equations , but define what $n$ should be. – Peter Aug 04 '23 at 13:05
  • How can $n$ be two things at once? – Nav Bhatthal Aug 04 '23 at 13:05
  • 2
    $n$ is not both at once. We assume that $n=k$ gives a true statement and look for the case $n=k+1$ whether the statement is again true. – Peter Aug 04 '23 at 13:08
  • 8
    Of course it isn't two things at once. We can evaluate a function, say, $f(x)$ at $x=1$ and at $x=2$. This does not suggest that $1=2$. similarly, we can evaluate a proposition $P(n)$ at different natural numbers. – lulu Aug 04 '23 at 13:08
  • So we look at the cases seperately? – Nav Bhatthal Aug 04 '23 at 13:09
  • I don't know what that means. In a typical inductive argument, we might assume that a proposition $P(n)$ has been demonstrated for $n≤k$ and then we seek to prove it for $n=k+1$. – lulu Aug 04 '23 at 13:10
  • To allude to your example, when we evaluate $f$ at $1$ and $2$, we do not think of $x$ being both $1$ and $2$ together, but there being different cases. – Nav Bhatthal Aug 04 '23 at 13:11
  • If it helps with intuition: I sometimes find it helpful to phrase inductive arguments as starting with "let $k$ be the least counterexample". After all, if the set of values $k$ for which $P(n)$ is false is a non-empty set of natural numbers, there must be a least $k$ for which $P(k)$ is false. You can then proceed to argue that , given a counterexample, you can always find a smaller one (contradicting the definition of least). – lulu Aug 04 '23 at 13:14
  • How would you justify $n$ not being two things at once then? If not for separate cases – Nav Bhatthal Aug 04 '23 at 13:14
  • 1
    Call them separate cases, if you like. I don't really understand what you mean by that as they are certainly connected. There is a single variable $n$ which can take multiple values, that's all. – lulu Aug 04 '23 at 13:18
  • Strictly speaking, there is no $n$. The statement that induction is trying to prove is $\forall n:\ P(n)$. That $n$ is a bound variable. Its scope is inside that proposition. It doesn't exist outside. The induction step is trying to prove $\forall k:\ P(k)\implies P(k+1)$. So you assume $P(k)$ and try to deduce $P(k+1)$. When people say "put n=k and prove for n=k+1", they are informally referring to the hypothesis and thesis of the universal instantiation of $\forall k:\ P(k)\implies P(k+1)$. Namely $P(k)\implies P(k+1)$. – NDB Aug 04 '23 at 13:21
  • Strictly speaking the $=$ in $n=k$ and in $n=k+1$ is not properly being used, but people understand. If they don't , they ask, like you, and are told. You pay with a small risk of confusion, for not having to write so much stuff. – NDB Aug 04 '23 at 13:22
  • I understand how to do induction, but this little bit always confused me, I knew there was more to it ! Thank you so much – Nav Bhatthal Aug 04 '23 at 13:24
  • Is the $=$ sign also not used properly when evaluating $f(x)$ then? Writing $x=3$ then $x=1$ seems similar to writing $n=k$ then $n=k+1$. @NDB – Nav Bhatthal Aug 04 '23 at 13:31
  • 2
    You have asked that before. – NDB Aug 04 '23 at 13:48
  • Figured it out, $n$ is just a "dummy" variable just as $x$ is in $f(x)$, thanks NDB, reading your previous answer on my old post really cemented this idea. – Nav Bhatthal Aug 04 '23 at 17:37

2 Answers2

1

I think you misunderstand what is meant here by "setting $n=k$". As you know, the goal is to show that some statement $P$ holds for all natural numbers $\mathbb{N}$, or more explicitly that $P(n)$ is true for all $n \in \mathbb{N}$. We establish in the base case that it holds for $1$, i.e. that $P(1)$ is true. The induction step is then to show that if $P(k)$ is true, then $P(k+1)$ is also true. Since we know that $P(1)$ is true, we would then get that $P(2), P(3), P(4),\dots$ are also true, showing that the statement $P(n)$ holds for all $n \in \mathbb{N}$. So, what they mean here by "$P(n)$ is true for $n = k$" is just an elaborate way of saying "$P(k)$ is true". They write it like that since it's more in the form of the "formal statement".

MXXZ
  • 1,123
0

What you are doing is sort of this:

Statement $1:$ At night, the sky is black.

Statement $2:$ During daytime, the sky is blue.

Statement $1$ contains "the sky is black".

Statement $2$ contains "the sky is blue".

Both statements are true.

Everything so far has been correct. Now comes the logical fallacy:

Logical fallacy:

Statement $3$: Therefore, black is blue.

The "logical fallacy" here, is that Statement $1$ and Statement $2$ are referring to different times of day, and so it makes no sense to "put them together" into Statement $3$. Indeed, we know Statement $3$ is false...

Adam Rubinson
  • 20,052
  • What is the "different time of day" in my example? The different cases for $n$? – Nav Bhatthal Aug 04 '23 at 14:00
  • Yes. $n=k$ is one scenario. $n=k+1$ is an entirely separate scenario. – Adam Rubinson Aug 04 '23 at 14:01
  • Can we evaluate $P(n)$ without knowing if $P$ is true for $n$? And then prove $P(k) \implies P(k+1)$? This would eliminate all my confusion. – Nav Bhatthal Aug 04 '23 at 14:03
  • $P(n)$ is a Truth statement about $n$; The statement $P(n)$ is either true or it is false. For example, I could define $P(n)$ to be the statement: "$n=1."$ By inspection, we see that $P(1)$ is true, but $P(n)$ is false for all integers $n>1.$ – Adam Rubinson Aug 04 '23 at 14:04
  • How is $P(k+1)$ defined then? Are we allowed to put any expression in place of $n$? – Nav Bhatthal Aug 04 '23 at 14:07
  • When you do induction, your aim is to show that, no matter what positive integer $k$ is, the statement $P(k+1)$ is true under supposition that $P(k)$ is true. – Adam Rubinson Aug 04 '23 at 14:10
  • I am asking if we can place any expression in place of $n$ in $P(n)$? – Nav Bhatthal Aug 04 '23 at 14:11
  • Yes you can. For example, sometimes when doing proof by induction, you might need to split the integers into even and odd numbers. One way to prove $P(n)$ is true for all even numbers, would be to first prove statement $P(2)$ is true, and then do the induction step, which would be to prove that if $k$ is even and $P(k)$ is true, then statement $P(k+2)$ is true. You would also need to prove $P(n)$ is true for all odd numbers: for the basis case you need to show $P(1)$ is true, and then do the induction step, which would be if $k$ is odd and $P(k)$ is true, then statement $P(k+2)$ is true. – Adam Rubinson Aug 04 '23 at 14:16
  • Then you would have proven $P(n)$ is true for all positive integers, right? – Adam Rubinson Aug 04 '23 at 14:16
  • Yes I agree, what do you think of my idea that $P(f(k))$ can be used to justify substituting $k+1$? Thanks for your feedback and answers. – Nav Bhatthal Aug 04 '23 at 14:18
  • I'm not sure what you mean by that. – Adam Rubinson Aug 04 '23 at 14:48
  • If we have a function like $f(x)$ we would say that $f(k+1)$ is the composition of $f$ and $g(k) = k + 1$, can we do something similar with $P$, as we did with $f$? – Nav Bhatthal Aug 04 '23 at 14:50
  • Hmm... It depends on exactly what you mean. Remember, $P(n)$ is a statement, so only in some very contrived sense can it be thought of as a function, I suppose. Can you give me an example of what you mean, and why you think it could be useful? As an aside, it seems to me that your intuition of mathematical induction is lacking. Can I suggest taking a look at just the top few paragraphs of wikipedia's explanation of what it is: https://en.wikipedia.org/wiki/Mathematical_induction – Adam Rubinson Aug 04 '23 at 15:19
  • I get quite far with understanding and then fall back down because of the $n=k$ then $n=k+1$ argument, I just can't justify in my head as to why its allowed, and I feel stupid for asking the same question over and over again to you guys. I'll take a read now. – Nav Bhatthal Aug 04 '23 at 15:22
  • To add some more context, I know if I was to substitute $k+1$ for $n$ in $(n+1)^2 = n^2 + 2n + 1$ I would need to know that it holds $\forall n$ which means it holds $\forall k$, the issue is when doing induction I do not know the range of validity for $n$, as that is what I am trying to prove – Nav Bhatthal Aug 04 '23 at 15:37
  • "I would need to know that it holds $∀n$ which means it holds $∀k$. " I don't understand what you mean by this. Shall we take this discussion to chat, as extensive discussion in comments is discouraged? – Adam Rubinson Aug 04 '23 at 16:09
  • Let us continue this discussion in chat. – Nav Bhatthal Aug 04 '23 at 16:10