James - 9 months ago 22

C++ Question

Discrete math is fun but I still have a lot of difficulty with the algebra involved. I am attempting to prove, through induction, a recursive function. I am just starting my course in algorithm design and the assignment was to rewrite an iterative function into a recursive function and then prove it. I was able to implement the recursive function and I was able to test it using a brute force technique, but I am at a loss as to how to set up my proof. I don't think I am starting it correctly. I included my start with the proof. Thanks for any pointers you can give me.

edit #3 final proof completed thanks to help

`f (k + 1) – f(k) =`

(k + 1) ^2 – ½ (k + 1) (k + 1 – 1) – k^2 – ½ (k (k -1)) =

k^2 + 2k + 1 – ½ (k^2 – k) – k^2 + ½ (k^2 - k) =

2k + 2 =

k + 1

edit #2 This is my proof so far and I am sure I am way off.

`Base Case, n = 1`

When n is 1, 1 is returned Line 1

1^2-(1*(1-1))/2 = 1

Inductive Case, n > 1

Assume for k = n-1, show for n = k

triangular_recursive(k) =

triangular_recursive (k -1) + k = Line 1

(k – 1) ^2 – ½(k-1) (k-1-1) + k = Inductive Assumption

k^2 -2k +1 – ½ (k^2 -3k +2) + k =

k^2 – k + 1 – ½ (k^2 -3k + 2)

This doesn’t see, correct at all.

Below is my code:

`/*`

JLawley

proof_of_correctness1.cpp

This provides a brute force proof of my algorithm

Originally, everything was integer type.

I changed to double when I added pow.

*/

#include "stdafx.h"

#include <iostream>

// this is the original function

// we were to rewrite this as a recursive function

// so the proof would be simpler

double triangular(double n) {

auto result = 0;

for (auto i = 1; i <= n; i++) result += i;

return result;

}

/*

* This is my recursive implementation

* It includes base case and post case

*/

// n > 0

double triangular_recursive(double n) {

return (n == 1) ? n : triangular_recursive(n - 1) + n;

}

// returns n^2 - (n(n-1)) / 2

// utility method to test my theory by brute force

double test_my_theory(double n)

{

return pow(n, 2) - (n * (n - 1))/2;

}

int main(void)

{

// at values much beyond 4000, this loop fails

// edit added - the failure is due to values too large

// the program crashes when this occurs

// this is a drawback of using recursive functions

for (auto i = 1; i <= 4000; i++)

if (test_my_theory(i) != triangular_recursive(i) || test_my_theory(i) != triangular(i))

std::cout << "\n!= at i = " << i;

// I am not getting any "i ="'s so I assume a good brute force test

return 0;

}

/*

* My proof so far:

Base Case, n = 1

When n is 1, 1 is returned Line 1

1^2-(1*(1-1))/2 = 1

Inductive Case, n > 1

Assume for k = n-1, show for n = k

triangular_recursive(k) =

triangular_recursive (k -1) + k = Line 1

(k – 1) ^2 – ½(k-1)(k-1-1) + k = Inductive Assumption

*/

Answer Source

A recursive function typically has a form something like:

```
recursive(param) {
if (base_case)
return base_value;
new_param = move_param_toward_base(param);
return combine(present_value, recursive(new_param);
}
```

An inductive proof basically has two steps:

- Prove some (usually trivial) base case.
- Prove some way of extending it, so that if the base case is true, your extended version remains true for some larger set of input.
- Prove that the extension can be applied more or less arbitrarily, so the result remains true for all inputs.

With a recursive function:

- You show that you've detected and treated the base case correctly.
- You show that your extension to some other value is correct.
- You show that you're modifying the parameter in a way that will lead to the base case in a finite number of steps.

But, there are also some differences, including the one you seem to be running into here. In particular, in mathematics, a non-modular number can grow without limit--but on a computer, all numbers are modular; none of them can grow without limit.