Wednesday, June 6, 2018

proof writing - Proving factorial by induction help



I really need help with proving this using induction.



\begin{align}
n! = [n(n-1) &\ldots (n-j+1)](n-j)!\ \ for \ 0 \le j \le n\\
\end{align}




I've tried using brute induction (which is what my prof calls it) and just using n = 1 first, then n = k+1. But I'm not sure what to do with the j? Please help. Anything will be appreciated. Thanks.


Answer



Well...



$(n+1)! = (n+1)*n! = (n+1)[n(n-1).....(n-j+1)](n-j)!; 0 \le j \le n$



$= [(n+1)n(n-1) ...... (n+1 - (j+1) + 1)](n +1 - (j+1))!$



$= [(n+1)n(n-1).........(n + 1 - i+ 1)](n+1 - i)!; 1\le i \le n+1$.




And $(n+1)! = [1](n+1 - 0)!; i=0$.



So .... that's it.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...