Explore BrainMass

# Induction on a Sum of Natural Numbers

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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 March 5, 2021, 12:30 am ad1c9bdddf
https://brainmass.com/math/number-theory/induction-sum-natural-numbers-512746

#### Solution Preview

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, ...

#### Solution Summary

A complete, detailed proof is provided.

\$2.49