Proof by induction (Recursion)

Question

Am really having a hard-time cracking this one. And no, its not homework. Am jst doing more examples in the textbook to see if i get the concept well

It says, we define the polynomial $P_n (x)$ for n being a member of all Natural numbers.

$$\begin{align} P_0 (x) &= 1\\ P_{n + 1} &= (x - 1)P_n (x) + x, n \geq 0 \tag{1}\label{eq1} \end{align}$$

1. Find $P_3 (x)$
2. Show that $P_n (3) = 2^{n+2} - 3$

Solving the first part, my approach was that i realized in $\eqref{eq1}$, we have $P_n (x)$ on the R.H.S. A few substitutions and divisions yielded the answer to be

$$\begin{align} \frac{P_{n + 1} - x}{(x - 1)} &= P_n (x) \tag{2}\label{eq2} \end{align}$$

I then used $P_3 (x)$ where the value of n was 3 to substitute in $\eqref{eq2}$ and i ended up with

$$\begin{align} P_3 (x) &= \frac{P_{3 + 1} - x}{(x - 1)} \\ &= \frac{P_{4} - x}{(x - 1)} \tag{3}\label{eq3} \end{align}$$
But i dont know if my interpretation is correct here coz i dont have the value of $P_{4}$

Part 2 defeated me miserably after trying it our on many A4 papers

Answer 1

It is clear that$$P_0(3)=1=2^{0+2}-3.$$On the other hand, if $P_n(3)=2^{n+2}-3$, then\begin{align}P_{n+1}(3)&=(3-1)P_n(3)+3\\&=2\times(2^{n+2}-3)+3\\&=2^{n+3}-3\\&=2^{(n+1)+2}-3.\end{align}

Answer 2

From $$ P_0 (x) = 1$$ and $$ P_{n + 1} = (x - 1)P_n (x) + x, n \geq 0 $$

You get,

$$ P_{ 1} = (x - 1)P_0 + x =2x-1$$

$$P_{2} = (x - 1)(2x-1) + x= 2x^2-3x+1$$

You can take over from here.

Answer 3

If you've seen the principle of induction and recursion before, you just need to do like it.

When something is defined recursively like, for example, the numerical sequence $u_{n+1}=u_n+1$ with $u_0=0$, you can conclude all the values of $(u_n)$ by going from the bottom: $u_0=0$ as given, then $u_1=u_0+1=1$, $u_2=u_1+1=2$, and so on...

So in your case, if you want to know $P_3$, get to it from the bottom: you know $P_0(x)=1$, thus $P_1(x)=(x-1)P_0(x)+x=2x-1$. Then use $P_1$ to get the value of $P_2$, and then use it to get $P_3$.

To prove 2., use the principle of induction.