0

I've been tasked to rewrite the following iterative function recursively:

int pentagonal(int n)
{
int result = 0;
  for (int i = 1; i <= n; i++)
   result += 3 * i - 2;
  return result;
}

Here is my attempt at doing so:

// n >= 1

int pentagonal(int n)
{
if (n == 1)
    return 1;
return pentagonal(n - 1) + 3 * n - 2;
}


// result = (3n^2 – n) / 2, or the pentagonal number at n

Now I am attempting to prove by induction that this recursive function is correct. Here is my reasoning:

Base case: When n is 1, 1 is returned. The first pentagonal number is 1, i.e. $(3(1)^2 – 1) / 2$ equals 1.

Inductive case: When n > 1, assume k, plug in k + 1:

The first term, "pentagonal((k + 1) – 1)", is merely the pentagonal at k, which is "3k – 2" k number of times, so we are left with $$ (3k – 2)(k) + 3(k + 1) – 2 = $$$$ 3k^2 - 2k + 3k + 3 – 2 = $$$$ 3k^2 + k + 1 = $$

But I am stuck here: $3k^2 + k + 1$ is not equal to $(3n^2 - n) / 2$.

I believe I may have made an error, but I don't really know where to begin. Is it in my math, my code, or both?

ganondork
  • 97

2 Answers2

0

You are using the wrong formula. It is not $(3k-2)k$. It is $k(3k-1)/2$.

The induction step is $k(3k-1)/2+3(k+1)-2 =(k+1)(3(k+1)-1)/2$ which is easy to verify.

marty cohen
  • 107,799
0

I believe my error arose from my failure to substitute the actual formula for the algorithm for my function ($pentagonal()$) (the "assume it's true" part of the inductive proof) and realize that the "step" part ($+3*n-2$) is separate from the $k-1$ "inductive hypothesis".

Proposed solution with this in mind:

This problem is easier if we assume $k-1$ is true and show the inductive "step" at k:

Inductive case: When $n > 1$, assume $k - 1$, plug in $k$: $$pentagonal(k – 1) + 3 * k – 2 ⇒$$ $$(3(k–1)^2 – (k–1)) / 2 + 3k – 2 =$$ $$(3(k^2 – 2k + 1) – k + 1) / 2 + 3k – 2 =$$ $$(3k^2 – 6k + 3 – k + 1) / 2 + 3k – 2 =$$ $$((3k^2 – 7k + 4) / 2) + (6k / 2) – (4 / 2) =$$ $$(3k^2 – k) / 2$$

ganondork
  • 97