Mathematical induction: propper use of assumption?

Question

Let $u_n$ be any recursive expression containing $u_{n-2}$. We are trying to prove that $u_n= f(n)$, where $f(n)$ is any well defined and not recursive expression of $n$.

Let's assume we know $u_1=f(1)$ and therefore we assume that $u_k = f(k)$. We now must prove that

$u_{k+1}=f(k+1)$ to conclude our induction. Because $u_{n-2}$ appears in the recursive definition of $u_n$, it's clear that $u_{k-1}$ will appear on $u_{k+1}$.

My question is: my hypothesis is only about $u_k$, but can't I apply it to $u_{k-1}$?

For example, if the case where that my hypothesis is $u_k=2^k$, can I conclude that $u_{k-1}=2^{k-1}$ when I'm trying to prove that $u_{k+1}=2^{k+1}$?

Answer 1

An explicit example would help, but I will write what I think you mean. To proceed with any induction proof, you have to determine the dependence of each case on the ones preceding it. So, if you are trying to prove that a certain relation holds for a certain $n$, you have to determine how many cases that precede it must hold in order to be able to deduce that it holds for $n$. Based on this, you can distinguish separate cases:

$(1)$ If it is possible to deduce the case $n$ only from $n-1$, then you only need to prove the case $n=1$ and this is the usual form of induction.

$(2)$ If, in order to deduce the case $n$, you need the preceding $m<n$ relations, you have to prove each case $m\ge i \ge1$ separately then proceed with the inductive step, namely, "Suppose the relation holds for the cases $n-1, n-2,....n-m$, we can prove that it holds for $n$ as follows....". Now your question lacks details so I can't fully apply this, but here are my thoughts, If you can prove the relation for $n=1$ but seem to need the preceding two cases to prove the case $n$, then you can do one of two things; either prove the relation for $n=0$ and proceed, or prove it for $n=2$ independently of $n=1$ and proceed, If you can't prove either, then there is no way to prove this by induction since you can't even prove it for the case $2$ or $3$ (depending on whether you will prove $n=0$ or $n=2$.)

Of course, these are not all the possibilities, for example, you may be able to prove $n$ using the case $n-2$, if so, you can proceed by induction for odd and even values of $n$ separately while keeping in mind that the relation may not hold for one of them, but the general idea is that you have to determine how many cases you need in order prove the one after them.

Answer 2

There are several possibilities to consider, depending on the particular situation. Here are some details, and basic examples, of the ones I can think of.

Case: $1$

One possibility is that $u_n$ is defined only for odd $n$, with $u_n$ for even values of $n$ being unspecified or unknown, and in particular not of a concern in the situation. For example, you may have $u_1 = 2$ and

$$u_{n} = 4u_{n-2}, \; \forall \; n = 2k + 1, \; k \ge 1 \tag{1}\label{eq1A}$$

In this case, assume your hypothesis is that

$$f(n) = 2^{n}, \; \forall \; n = 2k - 1, \; k \ge 1 \tag{2}\label{eq2A}$$

You then have $f(1) = 2^{1} = 2 = u_1$ as the base case, and you can use induction in steps of $2$ to prove your hypothesis.

Case: $2$

In this case, assume $u_n$ is defined for all $n \ge 1$. For this, as a base case, you will have to know $u_2$ fits whatever your hypothesis is. In addition, you will need to use something like strong induction in all $3$ sub-cases.

Case: $2$A

There's one basic function which can handle both the odd & even indices $n$ in $u_n$. For example, extending \eqref{eq1A}, assume you have $u_2 = 4$ and

$$u_{n} = 4u_{n-2}, \; \forall \; n \ge 3 \tag{3}\label{eq3A}$$

Your hypothesis would be an extension of \eqref{eq2A},

$$f(n) = 2^{n}, \; \forall \; n \ge 1 \tag{4}\label{eq4A}$$

You now have $2$ base cases to check, i.e., $f(1)$, as done earlier in case $1$, plus $f(2) = 2^2 = 4 = u_{2}$. Now, with strong induction, you assume \eqref{eq4A} is true for all $n \le k$ for some $k \ge 2$ and then prove it's true for $n = k + 1$.

Case: $2$B

In this case, the odd and even indices of $u_n$ have different behavior due to $u_2$ having an initial value which doesn't match the general case of extending the odd values. For example, reuse \eqref{eq3A} but assume $u_2 = 3$ instead. In this case, your would be an adapted version of \eqref{eq4A}, i.e.,

$$f(n) = \begin{cases} 2^{n}, & n = 2k - 1, \; k \ge 1 \\ 3(2^{n-2}), & n = 2k, \; k \ge 1 \end{cases} \tag{5}\label{eq5A}$$

Here, the base cases are $f(1) = 2^{1} = 2 = u_1$ works as shown before, and with $f(2) = 3(2^{2-2}) = 3 = u_2$. For the inductive phase, where you assume \eqref{eq5A} holds for all $n \le k$ for some $k \ge 2$, you will need to handle the case of $n = k + 1$ by checking whether $n$ is even or odd and handling these $2$ parity options somewhat separately.

Case: $2$C

In this sub-case, the definition $u_n$ has sub-parts, so its behavior for odd and even indices are different. For example, assume you have

$$u_n = \begin{cases} 4u_{n-2}, & n = 2k + 1, \; k \ge 1 \\ 9u_{n-2}, & n = 2k + 2, \; k \ge 1 \end{cases} \tag{6}\label{eq6A}$$

Assume $u_2 = 3$ again as in case $2$B. However, $f(n)$ is now defined as

$$f(n) = \begin{cases} 2^{n}, & n = 2k - 1, \; k \ge 1 \\ 3^{n-1}, & n = 2k, \; k \ge 1 \end{cases} \tag{7}\label{eq7A}$$

The base cases are $f(1) = 2^{1} = 2 = u_{1}$ and $f(2) = 3^{2-1} = 3 = u_{2}$, as before. Also, as in case $2$B, for the inductive phase, where you assume \eqref{eq7A} holds for all $n \le k$ for some $k \ge 2$, you will need to handle the case of $n = k + 1$ by checking whether $n$ is even or odd and handling these $2$ parity cases somewhat separately.

---

The above case examples are relatively simple, with most situations you encounter usually being more complex. Nonetheless, the basic principles outlined above will still hold in those situations.