Recursion Proof by Induction

Question

Given:

f(1) = 2
f(n) = f(n-1) + 3, for all n>1

It can be evaluated to:

f(1)=2
f(2)=f(2-1) + 3 = f(1) + 3 = 5
f(3)=f(3-1) + 3 = f(2) + 3 = 8
...

Or simply,

 f(n) = 3y-1 for all n>1

may be used to calculate f(n) directly.
For all n>1, f(n) follows +3 for every +n.

Next, the problem is to prove that my formula is correct through induction.
Below are my attempts.

Attempt#1

Prove:
3n – 1 for all n>1
    Base Case:
        n = 1, the sum is 2 and 3n-1 = 3(1)-1 = 2
    Inductive Step:
        Assume true for n=k: 3k-1
        Show true for n=k+1:
            3(k+1)-1
            3k+3-1
            3k+2
    Conclusion:
        by induction, the statement holds true for all n>1.

Not entirely sure if I am correct.

Attempt#2
Also tried using summation.
$\sum_{i=1}^n 2+3+3+3...+3 = 3n-1$ ... which didn't really work well for me.

Could you clear it up for me? Perhaps I am lost in the concept and/or overthinking this. One time I thought I got it, next thing I know I lost it when it comes to such different approach. In my attempts, I am also lost to the different situations whether I can/should use summation for it (being that this is not much of a sequence problem, rather just 2,3,3,3,3.., I wouldn't need to?)

Answer 1

Problems in Your Post

Let me first discuss the problems in your post.

• You wrote (I am $\LaTeX$'ing the text),

  Prove: $3n – 1$ for all $n>1$.

  Now, as it stands the statement doesn't make sense. What is it exactly that you want to prove? More specifically, what is(are) your premise(s)?

• Since you don't clearly state what exactly is that you want to prove, there is no sense in proving the Base Case and the Inductive Step. But still, assuming that you have now correctly stated what you want to prove, let me point out the problem in the statement that you wrote for the Base Case and the Inductive Step.

  In the Base Case you wrote,

  Base Case: $n = 1$, the sum is $2$ and $3n-1 = 3(1)-1 = 2$.

  Obviously the question is, what do you mean by "the sum is..."? Which sum are you referring to?

  In the Inductive Step you wrote,

  Inductive Step: Assume true for $n=k: 3k-1$. Show true for $n=k+1$, $$3(k+1)-1\\ 3k+3-1\\ 3k-2$$

  What exactly do we assume to be true for $n=k$?

• Your elaboration of second attempt is more confusing. Why exactly do you want to use induction here is not clear to me. Look below for what I guess you have attempted to do.

What (I think) Your Proofs Could be

Attempt 1

Prove: $P(n):=f(n)=3n-1$ is true for all $n\ge1$.

Base Case: $n = 1\implies 3n-1 = 3(1)-1 = 2=f(1)$. (So $P(1)$ is true.)

Inductive Step: Assume $P(n)$ to be true for $n=k$, i.e.,$P(k)=3k-1$. Now using this we need to show that $P(k+1)$ is also true. Now observe that, \begin{align}f(k+1)=f(k)+3&\implies f(k+1)=(3k-1)+3 \\&\implies f(k+1)=3(k+1)-1\end{align}which shows that $P(k+1)$ is also true. (Find out where we have used the Induction Hypothesis).

Conclusion: By induction, $P(n)$ holds true for all $n\ge 1$.

Attempt 2

Let $u_n=f(n+1)-f(n)$.

Prove: $P(n):=f(n)=\left(\displaystyle\sum_{i=1}^n u_i\right)-1$ is true for all $n\ge 1$.

Base Case: $n = 1\implies f(1)=\left(\displaystyle\sum_{i=1}^1 u_i\right)-1=u_1-1=2$. (So $P(1)$ is true.)

Inductive Step: Assume $P(n)$ to be true for $n=k$, i.e.,$P(k)=\left(\displaystyle\sum_{i=1}^k u_i\right)-1$. Now using this we need to show that $P(k+1)$ is also true. Now observe that, \begin{align}\left(\displaystyle\sum_{i=1}^{k+1} u_i\right)-1&=u_{k+1}+\left(\displaystyle\sum_{i=1}^k u_i\right)-1 \\&=u_{k+1}+f(k)\\&=(f(k+1)-f(k))+f(k)\\&=f(k+1)\end{align}which shows that $P(k+1)$ is also true. (Find out where we have used the Induction Hypothesis).

Conclusion: By induction, $P(n)$ holds true for all $n\ge 1$.

Though this doesn't directly yield your desired formula, you can obtain it simply by observing that $u_n=3$ for all $n\ge 1$.

Answer 2

Your proof never used your assumption (the inductive hypothesis). You need to use it.

Inductive Hypothesis: Assume that $f(k) = 3k - 1$ for some $k > 0$.

We want to show that $f(k + 1) = 3(k + 1) - 1$. Indeed, observe that: \begin{align*} f(k + 1) &= f(k) + 3 &\text{using the given recurrence, since } k + 1 > 1 \\ &= (3k - 1) + 3 &\text{by the inductive hypothesis} \\ &= 3k + 2 \\ &= 3(k + 1) - 1 \end{align*} as desired.

Answer 3

In your 2. attempt you have a strange way of using $\sum$. But I would also start from a similar point and then do a direct proof.

About $\sum_{i=n_0}^{n_1} t_i$ : I understand (define) the sum symbol like this:

1. if $n_0\le n_1$ $$\sum_{i=n_0}^{n_1}t_i = t_{n_1} + \sum_{i=n_0}^{n_1-1}t_i$$
2. else (if $n_0\gt n_1$) $$\sum_{i=n_0}^{n_1}t_i=0$$

So in your case we have to represent the recursive function as $f(n)=2+\sum_{i=2}^n3$

Now I can proof $\forall_n ( n\ge 1\to 2+\sum_{i=2}^n3=3n-1)$

1. assume $n\ge1$
2. to proof $2+\sum_{i=2}^n3=3n-1$
3. because the term inside the sum (3) does not depend on the index ($i$) it is clear that $\sum_{i=2}^n3=3(n-1)=3n-3$
4. if you add 2 you get $3n-1$