1

Prove by induction that the following equality holds true for all n that's an element of a natural number.

$$1\cdot 2+2\cdot 5+3\cdot 8+4\cdot 11+...+ n(3n-1) = n^2(n+1)$$

My work: Base Case: $n = 1$

l.s = 2

r.s = 2

True

Induction Hypothesis: Assume for some $k$ that's an element of a natural number, $$1\cdot 2+2\cdot 5+3\cdot 8+4\cdot 11+...+ k(3k-1) = k^2(k+1)$$

Now show that, $$1\cdot 2+2\cdot 5+3\cdot 8+4\cdot 11+...+ (k+1)(3(k+1)-1) = (k+1)^2((k+1)+1)$$

$$(k+1)(3k +2) = (k+1)^2(k+2) $$

$$3k^2 + 5k+ 2 = k^3 + 4k^2 + 5k + 2 $$

$$0 = k^3 + 4k^2-3k^2 + 5k - 5k + 2 - 2 $$

$$0 = k^3 + k^2 $$

by Induction Hypothesis, $k^3 + k^2 = k(3k-1)$

I know you're not supposed to start off with what you are trying to prove/show but if I reverse this whole process, wouldn't that be a correct proof? Is there a faster way? Thanks

mxian
  • 2,019
  • Thank you for recognizing that you should not start with what you want to show for the final proof, but it would still probably help you if you were to put that into practice immediately when beginning to work on the proof in the first place. There is no reason to rewrite everything twice when writing it just once would have been enough. As for your "proof" you seem to have lost track of the summation happening, having instead written things like $(k+1)(3k+2)=(k+1)^2(k+2)$ when it should have been $(1\cdot 2)+(2\cdot 5)+\dots+(k+1)(3k+2)=\dots$ – JMoravitz Apr 11 '17 at 20:08
  • So every time I have to bring (1⋅2)+(2⋅5)+⋯+ with me? –  Apr 11 '17 at 20:10
  • I don't really know how else to solve this question. –  Apr 11 '17 at 20:10
  • $\sum\limits_{k=1}^{n+1}(k(3k-1))=(n+1)(3n+2)+\underbrace{\sum\limits_{k=1}^n(k(3k-1))}=\dots$ the term with the underbrace you should be able to simplify by your induction hypothesis – JMoravitz Apr 11 '17 at 20:10
  • Oh ya, I guess I could just do that –  Apr 11 '17 at 20:10
  • Please consider using formatting – K Split X Apr 11 '17 at 20:16
  • As for the question of if there is a faster way, assuming you have already proven or have been given as an example $\sum\limits_{k=1}^nk=n(n+1)/2$ and that $\sum\limits_{k=1}^n k^2=(2n^3+3n^2+n)/6$, you can prove this directly by simply writing your summation as a linear combination of the triangle and the squarepyramidal summations. – JMoravitz Apr 11 '17 at 20:16
  • So would my original thought of reversing my work be incorrect? –  Apr 11 '17 at 20:30

2 Answers2

1

Your proof is incredibly confusing (not least due to lack of proper type-setting).

As you know, you really should just start on one side and try to get to the other side:

$$\sum_{n=1}^{k+1}(n(3n-1)) = $$

$$\sum_{n=1}^{k}(n(3n-1)) + (k+1)(3(k+1)-1)= $$ (Inductive Hypothesis)

$$k^2(k+1) + (k+1)(3(k+1)-1)= $$

$$(k+1)(k^2 + 3(k+1) -1) =$$

$$(k+1)(k^2 +3k+2)=$$

$$(k+1)(k+1)(k+2)=$$

$$(k+2)(k + 1)^2$$

So it is really only in the second to last step that I was looking at the goal ($(k+2)(k + 1)^2$) that told me I had to factor out a $k+2$, but other than that I just worked from left to right

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • instead of expanding the brackets in the inductive hypothesis, easier to take $(k+1)$ out to obtain $(k+1)(k^2+3k+2)=(k+1)^2(k+2)$ – farruhota Apr 17 '17 at 12:36
  • @FarrukhAtaev Yes, good suggestion! i'll update my answer, thanks! – Bram28 Apr 17 '17 at 13:43
0

The claim is as follows:

$$\sum_{k=1}^{n}k(3k-1)=n^2(n+1)$$

So consider the base case, that is, when $n=1$

Then:

$$\sum_{k=1}^{1}k(3k-1)=1(3(1)-1)=2 \ \checkmark$$

Assume the claim holds for the $n^{th}$ case, that is:

$$\sum_{k=1}^{n}k(3k-1)=n^2(n+1)$$

Then show it holds for the $(n+1)^{th}$ case:

$$\sum_{k=1}^{n+1}k(3k-1)=(n+1)^2(n+2)$$

So consider the following:

$$\sum_{k=1}^{n+1}k(3k-1)=\sum_{k=1}^{n}k(3k-1)+(n+1)(3(n+1)-1)=\sum_{k=1}^{n}k(3k-1)+(n+1)(3n+2)$$

Substituting our assumption, we have:

$$=n^2(n+1)+(n+1)(3n+2)=(n+1)(n^2+3n+2)=(n+1)(n+1)(n+2)=(n+1)^2(n+2)$$

Thus the $(n+1)^{th}$ case holds, given the $n^{th}$ case.

Therefore by induction, the original claim holds.

Mark Pineau
  • 1,400