4

I tried to find this answer on google and stackexchange but did not find any clue.

Why is it that we use another variable like $k$ in $P(k)$ rather than the original $P(n)$ in the inductive step of mathematical induction? Why can't we just use $n$? I think I am missing an important mathematical principle here...

Thanks.

R R
  • 1,084
user128344
  • 55

1 Answers1

4

Usually it is just for clarity. When doing a proof by induction we give a proposition that is quantified over $n\in \mathbb{N}$, such as "Let $P(n)$ be the statement...". It could be potentially confusing if we later said "Now assume $P(n)$ is true" for the purposes of showing the implication $P(n) \rightarrow P(n+1)$. We could certainly do it, but to be careful we would have to say something like "now pick an arbitrary $n$, and assume $P$ is true for that $n$". If you're clear at each stage what $n$ is it won't be a problem, but it can be a dangerous habit when you start having to deal with lots of different quantified variables. You could accidentally end up letting one variable mean two different things and then no one will be able to follow your argument.

R R
  • 1,084
  • Thanks, that's clearer. In some of the strong induction problems we've done in class, we use 2 more variables j and k in the inductive hypothesis, even when j and k are defined as 1 <= j <= k, k >= 1. It seems redundant to me, but is the reason still for clarity? – user128344 Feb 17 '14 at 02:47
  • 1
    Yes, in fact the $j$ is also reduntant. You could replace it by saying "for a fixed $n\in \mathbb{N}$ assume that $P(n)$ is true for all natural numbers up to and including this $n$". In fact I think its much clearer to write it that way, but I would still use $k$ rather than $n$ out of habit. To me using $k$ is making it more explicit that I'm assuming the hypothesis for a fixed value of $k$, because sometimes people get confused and think you're assuming $P(n)$ for all $n$ right off the bat, rather than assuming $P(n)$ for a fixed $n$. – R R Feb 17 '14 at 03:11