# Trying to find base case in recursive argument that a sequence with only finitely many peak indices has a monotone subsequence.

I'm examining an argument in Fitzpatrick's Advanced Calculus that a sequence $\{a_n\}$ with only finitely many peak indices has a monotone subsequence. His argument is shown below, with a modification that I added (in boldface). I'm not sure if his argument needs my modification or if my modification is even valid, but I felt like his recursive definition needs to address the base case. Please advise whether the modification is necessary, and why.

Since $\{a_n\}$ has only finitely many peak indices, we can choose an index $N$ such that there are no peak indices greater than $N$. We will recursively define a monotonically increasing subsequence of $\{a_n\}$. Indeed, define $n_1 = N + 1$. Now suppose that $k$ is an index such that positive integers $$n_1 < n_2 < \cdots < n_k$$ have been chosen such that $$a_{n_1} < a_{n_2} < \cdots < a_{n_k}.$$ We know that such an index $k$ exists, since $k=1$ satisfies this inequality. Since $n_k > N$, the index $n_k$ is not a peak index. Hence there is an index $n_{k+1} > n_k$ such that $a_{n_{k+1}} > a_{n_k}$. Thus, we recursively define a strictly increasing sequence of positive integers $\{n_k\}$ having the property that the subsequence $\{a_{n_k}\}$ is strictly increasing.

• The induction is on $k$. The supposition is the induction hypothesis. The base case is $k = 1$, with $n_1$ being explicitly [well, as explicit as $N$ is] chosen. – Daniel Fischer Aug 28 '14 at 20:21
• @DanielFischer Thanks! I guess I was just getting confused because he didn't specifically state that the base case is $k = 1,$ even though it's pretty clear. – justin Aug 28 '14 at 20:36

## 1 Answer

As suggested in the comment, the implied base case for the recursive definition is $k = 1.$