# prove recursive sequence via induction

I'm trying to prove a recursive sequence via induction. However, this question is quite different from what is being taught from the lecture. The basics of where I can assume a base case $n = 1$, and a case of $n - 1$ or $n + 1$ thereafter. Next, the question may provide like some basic formula like adding different cases to get a fixed formula to the sequence,

However, in this question

$𝑓_𝑛 = 0$ where $n = 0$, //may use this as a base case

$𝑓_𝑛 = 𝑓_{𝑛−1} + 𝑛$ where $𝑛 \ge 1$

What I attempt is to allow the first function $𝑓_𝑛 = 0$ where $n= 2$ , while the second function $𝑓_𝑛 = 1$ where $n = 1$, and the third function $𝑓_𝑛 = 3$ where $n = 2$.

I'm suppose to prove by induction that for all $n \ge 0$, the solution is $𝑓_𝑛 = (n^2 + n)/2$.

How do I even know how to combine them together without knowing any prior formula to this?

• It is quite illuminating to view the proof as an inductive proof of the uniqueness of the solution of the recurrence, e.g. see here.. Further, by telescopy, the solution can also be expressed as $\,\sum_{k=0}^n k\,$ if you already have (inductive) knowledge of such. – Bill Dubuque Jul 11 '17 at 14:47

OK, let's review what you know:

1. You know $f_0=0$.
2. You know that $f_n = f_{n-1} + n$ for $n\geq 1$.

You want to prove the claim

$$\forall n: f_n=\frac{n^2+n}{2}.$$

A proof by induction of a claim $P(n)$ (in our case, $P(n)$ is $f_n=\frac{n^2+n}{2}$) always has two steps:

Step 1:

Prove that the claim is true for $n=0$. In other words, you want to prove $P(0)$, in our case you want to prove $f_0=\frac{0^2+0}{2}$, which is fairly easy to prove.

Step 2:

Assume that $P(n)$ is true. Now you need to prove $P(n+1)$ is also true. In particular, you want to prove that $$f_{n+1} = \frac{(n+1)^2 + n+1}{2}$$ while you assume that $f_n=\frac{n^2+n}{2}$ is true.

You can now use the fact that $f_n = f_{n-1} + n$, which means the claim $$f_{n+1} = \frac{(n+1)^2 + n+1}{2}$$ (which you want to prove) is equivalent to $$f_{n} + n+1 = \frac{(n+1)^2 + n+1}{2}.$$

Now, just use the fact that you already know $f_n=\frac{n^2+n}{2}$ is true, plug in the value, and you are done.

• at step 2, if we assume n as n + 1, why is fn+1 = ((n+1)^2 + n))/2 instead of ((n+1)^2 + n+1))/2? – Bryan Jul 11 '17 at 13:08
• @TeoChuenWeiBryan Sorry, that was my typo. Of course the $+1$ was missing. – 5xum Jul 11 '17 at 13:08
• how do you "jump" from the fact that fn=fn−1+n to fn + n? – Bryan Jul 11 '17 at 13:15
• @TeoChuenWeiBryan I don't understand the question you just asked. Please use Mathjax to write out the formula you don't understand. – 5xum Jul 11 '17 at 13:16
• i have not tried using mathjax before. going to take me sometime to figure it out. – Bryan Jul 11 '17 at 13:22

You found the first few terms correctly. Note:

\begin{align} &f_0 =0, \\ &f_1 =1, \\ &f_2= 1+2, \\ &f_3=1+2+3, \\ &\cdots \\ &f_{n-1}=1+2+\cdots+(n-1) \\ &f_n \ \ \ \ =1+2+\cdots +(n-1)+n = \frac{1+n}{2}\cdot n \\ &f_{n+1} =\underbrace{1+2+\cdots +(n-1)+n}_{f_n}+(n+1) = \frac{1+n}{2}\cdot n+(n+1)= \frac{1+(n+1)}{2}\cdot (n+1). \end{align}

• how did you get the ((1+n)/2) x n for fn? – Bryan Jul 11 '17 at 13:03
• and how does fn+1 is the same as the solution fn ? – Bryan Jul 11 '17 at 13:05
• It is the formula of the sum of $n$ terms of the arithmetic progression. The formula works for $n+1$ too. – farruhota Jul 11 '17 at 13:08
• Note that this is not a strict proof, and a strict version of this proof would still have to use induction, first of all to prove that $f_n=1+2+\cdots + n$ and second of all to prove (if you didn't yet) that $1+2+\cdots+n = \frac{n(n+1)}{2}$ – 5xum Jul 11 '17 at 13:10
• @5xum, thanks. However, in the OP $f_n=(n^2+n)/2$ was given and asked to be proved. Here I gave some insight where the formula comes from and $\textit{used}$ induction to prove the formula. – farruhota Jul 11 '17 at 13:33