# Induction on a Sum of Natural Numbers

Let f:N x N -> N be the function defined recursively as follows:

f(0, 0) = 6

f(i, j) = f(i - 1, j) + 2 if i > 0 and j = 0

f(i, j) = f(i, j - 1) + 1 if j > 0

Use induction on the sum i + j to prove that f(i, j) = 2i + j + 6 for all (i, j) in N x N.

Â© BrainMass Inc. brainmass.com September 27, 2022, 6:00 pm ad1c9bdddfhttps://brainmass.com/math/number-theory/induction-sum-natural-numbers-512746

## SOLUTION This solution is **FREE** courtesy of BrainMass!

Please see the attached .pdf file for a complete solution.

Since i >= 0 and j >= 0, we have that i + j >= 0.

Base case: i + j = 0

In this case, (i, j) = (0, 0). By definition, f(0, 0) = 6, so

f(i, j) = f(0, 0) = 6 = 0 + 0 + 6 = 2(0) + 0 + 6 = 2i + j + 6

Induction step: Let k >= 1, let i, j in N be such that i + j = k, and assume (as induction hypothesis) that f(i' ,j') = 2i' + j' + 6 for all (i', j') such that i' + j' = k - 1. We will show that f(i, j) = 2i + j + 6.

There are two cases:

Case I: j = 0

Since i + j >= 1 and j = 0, we know that i >= 1. Thus i - 1>= 0 and

(i - 1) + j = i - 1 + j = (i + j) - 1 = k - 1

By the induction hypothesis,

f(i - 1, j) = 2(i - 1) + j + 6

By the definition of f(i, j) and the facts that i >= 1 (hence i > 0) and j = 0, we have

f(i, j) = f(i - 1, j) + 2 = [2(i - 1) + j + 6] + 2 = 2i - 2 + j + 6 + 2 = 2i + j + 6

Case II: j > 0

Since j > 0, we know that j >= 1 (hence j - 1 >= 0) and

i + (j - 1) = (i + j) - 1 = k - 1

By the induction hypothesis,

f(i, j - 1) = 2i + (j - 1) + 6

By the definition of f(i, j) and the fact that j > 0, we find that

f(i, j) = f(i, j - 1) + 1 = [2i + (j - 1) + 6] + 1 = 2i + j - 1 + 6 + 1 = 2i + j+ 6

https://brainmass.com/math/number-theory/induction-sum-natural-numbers-512746