2
$\begingroup$

I'm doing practise exam questions, and have got the following question :

Consider the function $\operatorname{five}: \Bbb N \to \Bbb N$ defined recursively as follows:

1) Base case: $\operatorname{five}(0) = 10$

2) Recursive case: $\operatorname{five}(x) = \operatorname{five}(x-1)+5$, for any $x>0$

prove using induction on the natural numbers that the following equality is true for all natural numbers $n \in \Bbb N$:

$$\operatorname{five}(n)=(n+2)*5$$

Here's what i've got down so far, but can't pass this point

Let $x=1 $

$$\operatorname{five}(1-1)=0 - 0+5 = 5 $$

Assume $x(k)$ holds $k+1$ must hold so the rest must hold...

I can't really write it in a mathematical way or get passed here=/ cheers in advance

$\endgroup$
1
  • $\begingroup$ I've edited your post to include MathJax; you can click the 'edit' link below your post to see what I changed. Please make sure that it says what you intended. $\endgroup$
    – user61527
    Commented Dec 21, 2013 at 23:21

3 Answers 3

Reset to default
0
$\begingroup$

Before we prove the result, it is worthwhile to compute a little. We are told that $\text{five}(0)=10$, and that for any $x\gt 0$, we have $$\text{five}(x)=\text{five}(x-1)+5.\tag{1}$$ Take $x=1$. Then the recurrence (1) gives $\text{five}(1)=\text{five}(1-1)+5=\text{five}(0)+5=10+5=15$.

Now let $x=2$. The recurrence gives $\text{five}(2)=\text{five}(1)+5=20$. Similarly we have $\text{five}(3)=25$. Now we have a pretty good idea of what's going on, so we can proceed to a formal proof.

For any non-negative integer $i$, let $A(i)$ be the assertion that $\text{five}(i)=(i+2)(5)$. We want to show that $A(n)$ is true for every non-negative integer $n$.

First we verify that $A(0)$ is true. Note that $\text{five}(0)=10=(0+2)(5)$. So indeed $A(0)$ is true.

Next we show that for any given non-negative integer $k$, if $A(k)$ is true then $A(k+1)$ is true.

So we are told that $\text{five}(k)=(k+2)(5)$. We want to show that $\text{five}(k+1)=((k+1)+2)(5)$. So we want to show that $\text{five}(k+1)=(k+3)(5)$.

By the recurrence (1), we have $$\text{five}(k+1)=\text{five}(k)+5.\tag{2}$$

By the induction assumption, $\text{five}(k)=(k+2)(5)$. So from (2) we get $$\text{five}(k+1)=(k+2)(5)+5=5k+10+5=5k+15=(k+3)(5).$$ That is precisely what we needed to show.

$\endgroup$
0
$\begingroup$

Suppose $f(n)=5(n+2)$ (1) is true for $n=k$. Then, we want to show that $f(k+1)=5(k+1+2)$. We know that $f(k+1)=f(k)+5=(5(k+2))+5=5((k+1)+2)$, so now we (1) is true for $n=k+1$, and thus, the induction step and proof are completed (because you did the 'base' step already yourself).

$\endgroup$
0
$\begingroup$

before trying the inductive proof, it may help to get a feel of what is happening to give the result required. as the recursive aspect of this problem is not very severe you you can use a simple trick:

write: $$five(1) = five(0) + 5 \\ five(2) = five(1) +5 \\ five(3) = five(2) +5 \\ five(4) = five(3) +5 \\ \dots \\ five(n) = five(n-1)+5 $$ adding these $n$ equations, you will see that most of the terms cancel, leaving $$ five(n) = five(0) + n*5 = 10 + n*5 = 2*5+n*5 = (2+n)*5 $$ (the $n*5$ is because you add 5 each of a total of $n$ times).

now the inductive step is to show that for $n+1$ what the formula just obtained "predicts" as the value of five$(n+1)$ is the same as what you get from the recursive definition.

from the definition we have: $$five(n+1) = five(n) + 5 $$ whereas from the formula, replacing $n$ by $n+1$ we have $$five(n+1)=(2 + \overline {n+1})*5$$

can you show that these two are the same?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .