Consider the following recurrence relation Pn 1 if n 0 Pn

Consider the following recurrence relation. P(n) = {1 if n = 0 P(n - 1) + n^2 if n> 0 Compute the first eight values of P(n). (Enter your answers as a comma-separated list of values ordered with respect to increasing n.) Analyze the sequences of differences. (Enter your answers as a comma-separated list of values ordered with respect to increasing n.) first differences: second differences: third differences: What does this suggest about the closed form solution? This suggests that the closed form will have degree. Find a good candidate for a closed-form solution. P(n) = Prove that your candidate solution is the correct closed-form solution. (Induction on n.) Let f(n) = Base Case: If n = 0, the recurrence relation says that P(0) = 1, and the formula says that f(0) =, so they match. Inductive Hypothesis: Suppose as inductive hypothesis that P(k - 1) = for some k> 0. Inductive Step: Using the recurrence relation, P(k) = p(k - 1) + k^2, by the second part of the recurrence relation = + k^2, by inductive hypothesis = so, by induction, P(n) = f(n) for all n greatrethanorequalto 0.

Solution

Part (a) : Here when n=0, then P(0)= 1

When n=1 , then p(n)= p(n-1)^2+n^2 =p(1-1)+1^2=p(0)+1=1+1=2

when n=2, then p(2)= p(1)+2^2= 2+4=6

when n=3, then p(3) = p(2)+3^2= 6+9=15

when n=4 , then p(4)=p(3)+4^2= 15+!6= 31

when n=5, then p(5) = p(4)+ 5^2= 31+25= 56

when n=6, then p(6)= p(5)+6*2= 56+ 36 = 92

when n=7, then p(7)= p(6) + 7^2 = 92+49 = 141

when n=8 = p(7) + 8^2 = 141+64= 205

So first eight values are 1,2,6,15,31,56,92,141,205

=================================================================================

Part(B) : First difference = 2-1= 1

second difference = 6-2=4

Third difference = 15-6 = 9

So as differences are 1,4,9,, ........... or 1^2,2^2, 3^2, 4^2,.............

So its closed form solution will have degree 2.

==================================================================================

Part (c) : By above facts, it is cleared that it is a second order linear recurrence.

So its auxilarry quadratic will be :