Purchase Solution

Induction on a Sum of Natural Numbers

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
Solution Summary

A complete, detailed proof is provided.

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 provided by:
Georgia Martin, PhD
Education
  • AB, Hood College
  • PhD, The Catholic University of America
  • PhD, The University of Maryland at College Park
Recent Feedback
  • "Thanks for your assistance. "
  • "Thank you. I understand now."
  • "Super - Thank You"
  • "Very clear. I appreciate your help. Thank you."
  • "Great. thank you so much!"
Purchase this Solution
Free BrainMass Quizzes
Probability Quiz

Some questions on probability

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

View More Free Quizzes
Related BrainMass Solutions

  • Well-Ordering Axiom - Strong Induction

    If P(1) is true and P(1) and P(2) and so on through P(n) imply P(n+1) then P(i) is true for all natural numbers. Proof of Well-ordering axiom by strong induction: We will do induction based on the size of the subset.

  • prove the proposition

    sum of the previous 2.

  • Induction Problem with Fibonacci Numbers

    the sum of the two previous numbers.

  • Hogatt's Theorem Proof

    Hogatt's theorem states that every positive integer can be expressed as a sum of distinct Fibonacci numbers. Fibonacci numbers satisfy: We prove by induction.

  • Proof : For every positive integer n, prove that 1+2+...+n=n(n+1)/2.

    statement is true for n=m+1 whenever it is true for n=m Hence by Principle of Mathematical induction, we say that the above statement is true for all natural numbers 'n'.

  • Mathematical induction

    (n + 1)} = n/(n + 1) see attachment This is a mathematical induction proof regarding sum of a series.

  • Mathematical Induction : How Would You Explain this to a Fellow Student?

    Ok, now k could be any natural number. k=2, then k+1=3. k=3, k+1=4...and so on. Therefore, it covers the entire natural numbers. The expert determines how you would explain mathematical induction to a student. Simplified term functions are given.

  • mathematical unduction

    Solution: We use Mathematical Induction to establish the truth value of some mathematical statements. The axiom, called Induction axiom, used is, if {P(n): n is a natural number} is a set of statements.

  • Proof : Equivalence Relations

    Hence the statement is true for n=k+1 Hence by principle of Mathematical Induction, we can say that the statement is true for all natural numbers n. Hence proved. An equivalence relation is proven. The solution is detailed and well presented.

View More Related Solutions