# Proving recursive formula via induction leads to extra term?

I have been asked the following question, and despite spending the last 30 minutes on it, have not come up with a good result:

Define $$f(1) = 2$$, and $$f(n) = f(n-1) + 2n$$ for all $$n \geq 2$$. Find a non-recursive formula for $$n$$, and prove by induction this formula works over all natural numbers.

So, this didn't sound too hard. I found the non-recursive formula to be $$f(n) = n^2 + n$$.

Base case of induction with $$n = 2$$:

$$f(2) = 2^2 + 2 = 6$$

Assumption step:

$$f(k) = k^2 + k$$

Extension step:

\begin{aligned} f(k+1) & = (k+1)^2 + (k+1) \\ & = (k^2 + 2k + 1) + (k+1) \\ & = f(k) + 2k + 2 \ (?) && (\text{Substitute} \ f(k)) \end{aligned}

Notice it all falls apart here? That extra "$$2$$" terms means any experimental result I plug in yields a value $$2$$ higher than it should.

What have I done wrong?

• You're almost done. By the recursive formula, what does $f(k+1)$ equal? Edit: It doesn't fall apart at all. Aug 10 '15 at 10:52
• The recursive formula would be f(k+1) = f(k) + 2(k+1)... ohh I see. I'm an idiot. Why did I miss that? Aug 10 '15 at 10:56
• @EchoLogic, happens to all of us sometimes. Aug 13 '15 at 18:30
• Please add your own answer to this question, completing the details of the above comments, and later accept it to close this question. Sep 3 '15 at 17:01

We have, the recursion formula, \begin{aligned} f(1) = 2, f(n) = f(n-1) + 2n && (1)\end{aligned}

and, the candidate, \begin{aligned}P(n): f(n) = n^2 + n && (2)\end{aligned}

### Step-1: (Base Case)

By $$(1)$$, we have:

$$f(1) = 2$$, and $$f(2) = f(1) + 2 \cdot 2 = 6$$

These are satisfied by $$(2)$$ also, via direct calculation. Hence, the base case is established.

### Step-2: (Induction Hypothesis/ Extension step)

Assume that the statement holds for $$n=k$$,

i.e. $$P(k): f(k) = k^2 + k$$, holds.

### Step-3: (Inductive step)

We now, prove $$P(k+1)$$, which is the subject of the question,

By $$(1)$$,

\begin{aligned} f(k+1) & = f(k) + 2 \cot (k+1) && (\text{Taking,} \ \ n= (k+1)) \\ & = (k^2 + k) + (2k + 2) && (\text{By the Induction Hypothesis}) \\ & = (k^2 + 2k + 1) + (k+1) \\ \implies f(k+1) & = (k+1)^2 + (k+1) \end{aligned}

Thus, $$P(k+1)$$ is established, contingent upon $$P(k)$$ holding.

By the Principle of Mathematical Induction, the formula $$(2)$$ holds.

## Notes:

A. The working presented in the OP has two flaws:

1. The failure to recognize that the expression in the last step has the formula was the desired result, minus taking a common factor. This had been pointed out by @Git Gud and recognized by the OP, in the comments.

2. The more important issue is that the presented working confounds the statement that is given to be true, eq. $$(1)$$, and the one that is to be proved, eq. $$(2)$$. Specifically, the induction hypothesis assumes $$P(k)$$, so that the next step should be to establish $$P(k+1)$$. However, the OP assumes $$P(k+1)$$ in accordance with $$(2)$$, and tries to show how this implies $$(1)$$. Now, this works for the present case as all the operations involved are bidirectional $$(\iff)$$. Thus,we do indeed show that $$(1)$$ implies $$(2)$$, establishing $$P(k+1)$$. However, this is poor form that disrupts the flow of the logic and can lead to trouble if one is dealing with problems regarding say, inequalities. Although working backwards is a legitimate strategy that can be very useful, it requires care to ensure that the reversed steps are valid and useful, and is, at any rate not required here.

B. The notation $$P(k)$$, indicates the statement, $$P(n)$$, that is, ($$f(n) =n^2+n$$), for the case $$n=k$$. $$P(n)$$ is the statement that in the general case that there is an arbitrary $$n \in \mathbb{N}$$, we have $$f(n) = n^2 + n$$. This is a standard notation (albeit not one mentioned in OP's working in the question) in problems where mathematical induction is used, among others.

C. While mathematical induction can be useful for proving true statements over $$\mathbb{N}$$ (and many other cases, including well-founded sets in general), it is not nearly as useful in detecting the invalidity of false statements, and does not the address the important problem of generating plausible statements to check. Indeed, generating the formula is the first part of the problem the OP set out to solve. In the case, the formula was (almost certainly by design), trivial to guess. However, the generation of such statements. and particularly finding explicit formulae for recurrence relations; can be a very challenging problem to solve, and offers an interesting counterpoint to the problem of solving differential equations over $$\mathbb{R}$$ or $$\mathbb{C}$$. While a full discussion would be wildly out of scope here, it is interesting to note that here: $$\frac{f(n)-f(n-1)}{n-(n-1)} = 2n$$ which is reminiscent of the derivative over $$\mathbb{R}$$ and suggesting the appropriate solution should be a quadratic polynomial, as is indeed the case. It is left to the reader to verify that modifying the initial condition leads to solutions of the form $$n^2 + n + f(1) - 2$$.