0

Let the function ${\rm five}(n)$ be a function defined by the two equations:

${\rm five}(0) = 10 \\ {\rm five}(n+1) = {\rm five}(n) + 5$

Prove that: ${\rm five}(j) = 5*(j + 2)$ for all non-negative integers $j$.

I asked a friend today a question about proof by induction and he gave me the working out. I understand the majority of it until the very end if someone could indicate me where it's coming from

Base case - five(0) = (0+2)*5=10 => holds

Assume five(k) = ( k+2 )*5 holds up to some point k

prove for k+1

five( k + 1 ) = ((k + 1 ) + 2 )*5

five( k + 1 ) = five( k ) + 5 = ( k + 2 )*5+5

True for all for of k

The point highlighted is where I become lost

Caleb Stanford
  • 45,895
user119325
  • 127
  • 1
  • 6
  • 1
    Is the five(o) supposed to represent $5(0)=5\times 0=0$? If so, the hypothesis is false... – Clayton Jan 06 '14 at 21:12
  • The line just before your highlight is "what needs to be shown". So we know that five$(k)=(k+2)\cdot 5=5k+10$ and if we take five$(k)+5$ we get five$(k)+5=5k+15=5(k+3)=5(k+2+1)=$five$(k+1)$. – abiessu Jan 06 '14 at 21:17

1 Answers1

1

You've left out something big in your question. I'll try to reconstruct what fits in this hole, but I may be missing something.

Namely, I don't understand how this function 'five' that you're talking about is defined, or what you're trying to prove. Here's what I think you're saying:

Let the function ${\rm five}(n)$ be a function defined by the two equations:

${\rm five}(0) = 10 \\ {\rm five}(n+1) = {\rm five}(n) + 5$

Prove that: ${\rm five}(j) = 5*(j + 2)$ for all non-negative integers $j$.

Okay, so given that, here's what's going on at the stage where you get lost:

  • We've already proved it for $j=0$. Now, we're going to assume that the formula holds for $j =$ some value $k$. That is, we assume that ${\rm five}(k) = 5*(k + 2)$ works for some $k$, and we're going to prove that the formula still works for $j = k + 1$.

  • First: $$ {\rm five}(k+1) = {\rm five}(k) + 5 $$ This is from the definition of ${\rm five}$ above.

  • Using our induction hypothesis (some books call this "the induction assumption") to replace ${\rm five}(k)$: $${\rm five}(k) + 5 = (5 * (k + 2)) + 5$$

  • Now it's just straightforward algebra to rearrange that: $$ (5 * (k + 2)) + 5 = 5 * ((k + 1) + 2) $$

  • And so we have proven that the formula hold for $j = k+1$ if we assume that it holds for $j=k$.

  • Now by induction, we have proved the formula for all natural numbers $j$.

Community
  • 1
Daniel Martin
  • 919