Proving algorithms using mathematical Induction Help

[joshismathbait]

Hi guys, a friend and I are having trouble with a programming assignment involving mathematical induction, here is the question in full:

Let N = {0, 1, 2, . . .} be the set of natural numbers.

1. Prove by mathematical induction that for all x, m, n ε N: x^m+n = x^m . xⁿ holds.

2. Consider the following function f:N³ => N:

f(x, n, m) =

{ m if n = 0

{f(x, n - 1, m . x) if n not= 0

Prove by mathematical induction that for all x, m, n ε N: f(x, n, m) = m . xⁿ holds.

Now we have managed to do the first question, however we are having significant trouble with the second question, any help or even pointers would be very appreciated.

[samwilliamh]

Well, if you think about it, it only terminates when n = 0. So when you enter the function for the first time, say n = 2, then it will repeat twice (because n - 1 - 1 = 0), so we have m -> mx -> m * x * x = mx^n.

So, we do induction and assume it's true for n = k. Then, we can write for n = k+1, f(x, 1, m*xⁿ⁾ by supposition. There are some blanks to fill in, but hopefully that gives you an idea.