COT 3100 Intro. To Discrete Structures Problem 1: Assume that n is a positive integer. For each of the following algorithm segments, how many times will the innermost loop be iterated when the algorithm segment is implemented and run? (5 points for each) 1. for k :1 to n for = 1 to k for i1 toj [Statements in the body of the inner loop, none containing branching statements that lead outside the loop) next i next next k 2. for k :1 to n for j:-1 to k - 1 for i1 to j -1 Statements in the body of the inner loop, none containing branching statements that lead outside the loopl next i next next k Problem 2 (10 points): Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence a,-2aK-1 +3aK-2 a,-1, a,-2 for all integers k 2 Problem 3 (10 points): Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence ak 6ak-1- 9ak-2 for all integers k22 a,-1, al 3