Question

Main topic and problems for the final project The main purpose of the project is to introduce you how to use a computer as a research tool in an Introductory Discrete Mathematics. In this project you will be asked to show how the Fibonacci sequence (F,) is related to Pascal's triangle using the following identities by hand for small n and then by computers with large arguments, such as inductions or combinatorics Finally to rove the identity by mathematical n. Σ)- F where F, is the t-th term of the Fibonacci sequence. Hint: In that the sum of the diagonals of Pascal's triangle are equal to the corresponding Fibonacci sequence term. That is the values on the diagonals of Pascal's triangle add up to the Fibonacci numbers.] Problems: e (1,2,...,7). large n e {1,2,..., 100). (1) By hand, show that the above identity is true for some small (2) By computer, show that the above identity is true for some (a) Write (b) Write a program with any language to print out for the right-hand side of the identity. (c) Compare the result from part (a) and (b) for some large n e {1, 2,..., 100). (3) Prove the identity by mathematical induction by hand. (4) Prove the identity by combinatorial arguments. program with any language for the left-hand side of the identity a Extra-Credit Problme: All or None Prove the identity by mathematical induction with computers. REFERENCES

Discrete Math and Computer Science
I need help with #2 the programming part is in C++ Thank you!

Answer 1

Answer 2:

(a)

/**
 * Program for Left Hand Side
 */

#include <iostream>
#include <cmath>

using namespace std;

long long factorial(long long n){
    if(n <= 1)
        return 1;
    return n * factorial(n - 1);
}

long long sigma(long long n){
    long long sum = 0;
    for(int k = 0; k <= floor(n/2); k++){
        sum += factorial(n - k)/(factorial(k) * factorial(n - 2*k));
    }
    return sum;
}

int main(){
    int n = 20;
    cout << "Left Hand Side for n = " << n << " = " << sigma(n) << endl;
    return 0;
}

(b)

/**
 * Program for Right Hand Side
 */

#include <iostream>

using namespace std;

long long F(int n){
    if(n <= 1)
        return n;
    return F(n - 1) + F(n - 2);
}

int main(){
    int n = 20;
    int t = n + 1;
    cout << "Right Hand Side for t = " << t << " = " << F(t) << endl;
    cout << "Here t = n + 1" << endl;
    return 0;
}

(c)

For n = 20

Output from (a)

untitled2X C: \Users Shubham CLion Projects\untitled2 \Cmake-build-debug\untitled2.exe Left Hand Side for n = 20 = 10946 Process finished with exit code 0

t = 21 because t = n + 1 and n = 20

Output from (b)

C:\Users\Shubham\CLionProjects \untitled2\ cmake-build-debug\untitled2.exe Right Hand Side for t= 21 = 10946 Here t n + 1 Process finished with exit code 0