Help me Prove this Math Induction Problem.

[Scrapster]

Let f: R -> R (real numbers) be a function such that f(x+y) = f(x) + f(y) for
x, y "belonging to" R (real numbers).

a) Prove that f(0) = 0
b) Prove that f(n) = nf(1) for all n "belongs to" N (natural numbers)

I've done induction with inequalities and summations, but I'm not really sure how different the method is when we are dealing with f(x) and f(y). Does anyone have suggestions?

 

[Napalm381]

(a)f(0) = f(0+0) = f(0) + f(0) => f(0) = 0. (subtract f(0) from both sides).

(b) f(n) = f(1) + f(n-1) = 2*f(1) + f(n-2) = ..... = n*f(1)

 

[Scrapster]

Napalm,

Can you explain what you did. Especially for b) ?

 

[Cerebus451]

Induction proof for f(n) = n*f(1) would go like this:

Suppose f(n) = n*f(1)
f(n + 1) = f(n) + f(1) by definition
f(n + 1) = n*f(1) + f(1) by supposition
f(n + 1) = (n + 1) * f(1) by factoring

Thus, through induction, f(n) = n * f(1)

Since f(n) = n * f(1), f(0) = 0 * f(1) = 0

 

[StormRider]

Hahaha, you make me laugh Scrapster. I was a TA in a Discrete Math course once and now I'm wondering if any of my former students used Anandtech to do their homework! Shame, shame!

Anyways, in using Induction, there are always 2 things we need to show. We need to show the base case holds and we need to prove the Induction step.

We will use Induction to prove the statement: f(n) = nf(1) for all n "belongs to" N (natural numbers).

We want to show the above statement is true for the Base Case where n = 0. In other words we want to show:

a) f(0) = 0*f(0) which is the same as f(0) = 0

The other guy showed how to do this and you indicated you understood this step.

Now we need to show the Induction Step. In other words, we need to show that the following statement is true:

If f(n) = nf(1) then f(n+1) = (n+1)f(1)

How do we always show that an IF-Then statement is true?

Well, we assume the first part is true. In other words, we *assume* that

f(n) = nf(1) is true

Now we need to prove that f(n+1) = (n+1)f(1) is also true.

Here goes:

f(n) = nf(1) // Because we *assume* this is true
= nf(1) + f(1) - f(1)
= (n + 1)f(1) - f(1)

Now we bring the f(1) to the left hand side

f(n) + f(1) = (n + 1)f(1)

But we also know that f(x + y) = f(x) + f(y) for any x,y so we know that f(n) + f(1) = f(n+1). Therefore:

f(n+1) = (n+1)f(1)

That's what we needed to show!

By the Principle of Mathematical Induction, we have proved that

f(n) = nf(1) for all n "belongs to" N (natural numbers).

QED.

 

[StormRider]

Cerebus showed it better than I did for the 2nd part....