Question

Consider the following recurrence relation.
P(n) =
0 if n = 0
[P(n − 1)]^2 − n if n > 0
Use this recurrence relation to compute P(1), P(2), P(3), and P(4).

Answer 1

\[P(n) =\begin{cases}0 & n = 0\\ [P(n-1)]^2-n & n > 0\end{cases}\]

Let's do P(1)
Since n = 1 in this case, we will use P(n) = [P(n-1)]^2-n, i.e.
P(1) = (P(0)) ^2 - 1
Consider the P(0) on the right, we know that n=0, so, P(0) = 0, then we get
P(1) = (P(0)) ^2 - 1
= 0^2 - 1
= ...

Can you complete P(1) and try the rest now?

Answer 2

plug n=1,2,3,4 in p(n)=[P(n-1)]^2-n
but first find P(1) and so on

Answer 3

What I don't understand is how did we start at p(0).

Answer 4

it is already given P(0)=0

Answer 5

So P(1) would equal a = -1?

Answer 6

P(n)=0,for n=0
or P(0)=0

Answer 7

P(1) is equal to -1, yes.

Answer 8

The principle of recurrence is to find the value of a function with a large input by finding the value of the function with a smaller input.

For example, in your case,