Thursday, October 29, 2015

discrete mathematics - Proof By Induction: Summation of Polynomial

Prove by induction (weak or strong) that:



$$\sum_{k=0}^{n-1}(k + 1)^2= \frac{n(n + 1)(2n+1)}{6}$$




My base case is:



$n = 1$, which is true.



In my Inductive Step, I assume that: $$S(n)=\frac{n(n + 1)(2n+1)}{6}$$ holds for an arbitrary value of $n$.



Proving it then holds for $n+1$:
$$ S(n+1)=\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$$
$$ \phantom{S(n+1)}=\frac{(n+1)((n+2)(2n+2+1)}{6}$$
$$ \phantom{S(n+1)}=\frac{(n+1)((n+2)(2n+3)}{6}$$

$$ \phantom{S(n+1)}=\frac{2n^3+9n^2+13n+6}{6}$$



but can't see how my definition of $S(n)$ can be substituted into this final equation?



[EDIT] This isn’t a duplicate because the original summation of $(k+1)^2$ is what I’m originally provided with. The apparent duplicate question also doesn’t have a correct proof by induction answer associated with 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...