Instructions: Complete the following Proof of Correctness exercises and submit your answers.

Question 1: Given the following recursive algorithm for determining the Fibonacci numbers for any given value of n: int fibo(int n) { if(n < = 1) return n; else return fibo(n-1) + fibo(n-2); }

Question 2: Include its pre-conditions and post-conditions. Finally, prove by induction that the recursive algorithm is correct Given the following iterative algorithm which computes the nth triangular number: int tri(int n) { int result = 0; for (int i = 1; i = n; i ++) result += i; return result; } Convert this function to use recursion. Include its pre-conditions and post-conditions. Finally, prove by induction that the recursive algorithm is correct