I'm currently learning to prove something via induction. I have two questions:

1) In the inductive step, assuming that the statement $P(k-1)$ holds, so that you have to show that $P(k)$ follows, how exactly has the induction hypothesis to be formulated? Like this:

"The statement $P(k)$ holds for some $k\le n-1.$" ? I guess there should be no difference between this 'variant' and this one where you assume $P(k)$ and then have to show that 'P(k+1)' in the inductive step, because it is

$$\big(P(k)\Rightarrow P(k+1)\big)\;\iff \big(P(k-1)\Rightarrow P(k)\big),$$right?

2) In the induction base, I'm still not sure in which cases I have to do verify the statement for more than one n, (i.e. not only n=0, but also n=1) and so on.. can you explain me typical situations in which I have to verify the statements for several n's for the induction base?

Thank you for any help.

  • $\begingroup$ simple or completle induction? $\endgroup$ – K Split X Aug 16 '17 at 22:08
  • $\begingroup$ $\big(P(k)\Rightarrow P(k+1)\big)\iff \big(P(k-1)\Rightarrow P(k)\big)$ is not always true. For example it is false when $P(n)$ means "$n$ equals seven" and $k$ is $7$. $\endgroup$ – Henning Makholm Aug 16 '17 at 22:08
  • 1
    $\begingroup$ Recommended reading: how to write a clear induction proof $\endgroup$ – JMoravitz Aug 16 '17 at 22:09
  • 1
    $\begingroup$ In your statement in 1), "The statement P(k) holds for some k≤n−1.", what is supposed to be n? $\endgroup$ – Keen Aug 16 '17 at 22:11
  • $\begingroup$ As for when you need multiple base cases, this will sometimes occur when whatever observation or pattern you wish to point out does not work or is not well defined for too small of cases. For example "Prove that $T(n)$ is always an integer for all integers $n\geq 0$ where $T(n)$ is the tribonnaci sequence $T(0)=0,T(1)=0,T(2)=1,T(n)=T(n-1)+T(n-2)+T(n-3)$ for $n>2$." Here, in our inductive step, we wish to use the recursive nature of the tribonacci numbers that it is the sum of the previous three tribonacci numbers however that isn't true for the first three so we need $n=0,1,2$ as base cases. $\endgroup$ – JMoravitz Aug 16 '17 at 22:14

First of all I applaud you for the username.

I'll do an induction proof for you, and show you why I do everything. Hopefully this will answer all your questions.

Suppose we have the following:

$$ f(n) = \left\{\begin{array}{lr} n, & \text{for } 0\leq n\leq 2\\ 3f(n-2)+2f(n-3), & \text{for } n>2\\ \end{array}\right\} $$

Let's prove $f(n)<2^n$ for all $n\in\mathbb{N}$

Let's define a predicate.

For all $n\in\mathbb{N}$, let $P(n):f(n)<2^n$

Pf of $\forall n, P(n)$.

Base case(s)

First of all, notice the when we recurse ($n>2$), we have to "go back" at most $3$ numbers, hence the $n-3$. This should suggest that we have $3$ base cases.

As for which ones, well definitely we must prove $P(0)$, and after that, we prove 2 more, so we prove $P(1),P(2)$. So in the inductive step, when we "go back", we have these base cases to work with, so we are okay. If you only proved $P(0)$, then in the inductive step you would get stuck, because you don't know anything regarding $P(n-2)$.

Let $n=0$

Then $f(n)=0$, by definition

$< 2^0 = 1$

$\therefore P(0)$ holds.

Now do $P(1)$ and $P(2)$

Induction Step: For of all, since we proved $P(0-2)$, now we let $n>2$, or equally $n\geq 3$, so we enter the induction step.

Let $n>2$

Suppose $P(j)$ holds where $0\leq j\leq n-1, j\in\mathbb{N}$. [IH]

What does this say? This says let $j$ be an arbitrary natural number between $0$ and $n-1$, both inclusive. This says that suppose $P(0)\land P(1)\land\dots\land P(n-1)$ hold. This is how I write my IH, it's very clear. Moreover, you can also write this:

Suppose $P(j)$ holds where $0\leq j\lt n, j\in\mathbb{N}$. [IH]

We want to prove that $P(n)$ holds. It's much easier to prove $P(n)$ holds, rather then assuming $P(n)$ and proving $P(n+1)$.

$f(n)=3f(n-2)+2f(n-3)$, by definition of recursive step

$<3\cdot 2^{n-2}+2\cdot 2^{n-3}$, by IH, since $0\leq n-3<n-2<n$

$=6\cdot 2^{n-3}+2\cdot 2^{n-3}$

$=8\cdot 2^{n-3}$


$\therefore P(n)$ holds.

We have showed it holds for all $\mathbb{N}$, and so our proof is done. For proving how many base cases, think about how many steps the recursion "goes back", and proceed from there. For writing your induction hypothesis, it becomes much easier with a predicate and proving $P(n)$. If you can understand the way I wrote mine, just use that. Assume the predicate holds within that range, where $0$ is your first base case, and $n-1$ is what you assume it holds to. Then prove $P(n)$. Hope you found this answer useful.

  • 1
    $\begingroup$ (+1) for the effort and wow, this really helped my write my IH better too. Thanks! $\endgroup$ – VD18421 Aug 16 '17 at 22:33

Assume you want to prove that

$$\forall n\ge n_0 \;\;P_n $$

In the induction base, you check that the first $P_{n_0} $ is true.

In the inductive step , you start like this :

Let $n\ge n_0$ such that $P_n $. then you prove $P_{n+1} $.

  • $\begingroup$ Life is weird. What about the OP? This was a really good question about legitimate confusion by a sincere student trying to understand. And it gets 2 downvotes???? Weirdos on this site. $\endgroup$ – fleablood Aug 16 '17 at 22:52
  • $\begingroup$ @fleablood I gave an intresting answer but some special users downvoted . $\endgroup$ – hamam_Abdallah Aug 16 '17 at 22:59
  • 1
    $\begingroup$ I don't understand these downvotes either (and I don't care about the downvotes), I'm happy to get some really helpful answers which help me to understand everything better. As soon I'm able to upvote, I will upvote your answer. $\endgroup$ – user472520 Aug 17 '17 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy