Потерянный в Доказательстве для Рекурсивной функции

Дискретная математика — это весело, но я все еще испытываю трудности с алгеброй. Я пытаюсь доказать посредством индукции рекурсивную функцию. Я только начинаю свой курс по разработке алгоритмов, и мне было поручено переписать итеративную функцию в рекурсивную функцию, а затем доказать это. Мне удалось реализовать рекурсивную функцию, и я смог протестировать ее, используя метод грубой силы, но я не знаю, как настроить мои доказательства. Я не думаю, что я начинаю это правильно. Я включил мое начало с доказательством. Спасибо за любые указатели, которые вы можете дать мне.

редактировать # 3 окончательное доказательство завершено благодаря помощи

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 + 1 - k =
k + 1

edit # 2 Это мое доказательство до сих пор, и я уверен, что я далеко.

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.

Ниже мой код:

    /*
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
*/