Friday, 5 February 2016

discrete mathematics - Proof by induction (Recursion)



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



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}


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...