Saturday, 7 January 2017

discrete mathematics - Proof by induction that $(1^3 + 2^3 + 3^3+cdots+n^3) = (1 + 2 + cdots + n)^2$




I'm sitting with the proof in front of me, but I do not understand it.




$$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$



The first step of proof by induction is simple enough,to prove that $1 \in A$



$1^3 = 1^2$



The next step is where I get tripped up. So I add $n + 1$ to the right hand side



$$(1 + 2 + \cdots + n + (n + 1))^2 = (1 + 2 + \cdots + n)^2 + 2(1 + 2 + \cdots + n)(n + 1) + (n + 1)^2$$




My algebra is failing me here, because I do not understand how the equation was expanded.


Answer



The last step uses the identity:
$$(a + b)^2 = a ^2 + 2ab + b^2$$



So:
$$(\underbrace{1 + 2 + \cdots + n}_a + \underbrace{(n + 1)}_b)^2 =\\= (1 + 2 + \cdots + n)^2 + 2(1 + 2 + \cdots + n)(n+1) + (n + 1)^2\tag{1}$$



By induction hypotesis we have that $(1 + 2 + \cdots + n) ^2 = (1^3 + 2^3 + \cdots + n^3)$. We also use another identity, namely $(1 + 2 + \cdots + n) = n(n+1)/2$.




Combining those two facts and substituting into $(1)$:
$$(1^3 + 2^3 + \cdots + n^3) + 2\times n(n+1)/2 \times (n + 1) + (n+1)^2 = \\(1^3 + 2^3 + \cdots + n^3) + n(n+1)^2 + (n+1)^2 =\\1^3 + 2^3 + \cdots + n^3 + (n + 1)^3$$



$\blacksquare$


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}...