2

Here is what we are given

Use induction to show that for all $x$ $\in$ $\mathbb{Z}^+$ $$\sum_{j=1}^x (4j - 1) = x(2x+1)$$

This is what I have done

Sometimes I find sigma notation a little confusing but here is my expansion of the question:

$$(4*1 - 1)+(4*2 - 1)+...+(4(x-1)-1)+(4x-1) = x(2x+1)$$

Proof (By Induction):

Base Case:

$$n = 1$$

LHS $$= (4*1) -1 = 3$$

RHS $$= 1(2+1) = 3$$

Therefore, the base case holds and we can continue with the inductive step.

Inductive Hypothesis:

Show that if $$x = k \space \text{holds, then} \space x = k + 1 \space \text{also holds}$$

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

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

Now, I've dun' goof'd somewhere. I can't reconcile this algebraically which leads me to the conclusion I need to look harder...or there may be an error in my expansion of the sigma notation or the substitution of $x = k$ and $x = k+1$.

I'm assuming there are many on this forum which will find this question easy, may I borrow your intellect? I may only need a few pointers to get the ball rolling.

$$THANK \space YOU$$

Rubicon
  • 616
  • 3
    The $k+1$ term is not $4k+1-1$, it is $4(k+1)-1$ – almagest Apr 18 '16 at 13:18
  • There is an easier way to do this that doesn't require induction: Specifically notice that $\sum_{j=1}^{n} j=\frac{n(n+1)}{2}$. Please tell me if you want me to make this an answer. – zz20s Apr 18 '16 at 13:19
  • Thank you, but the question requires me to use induction as my method :). Just reading all these answers now and processing them. – Rubicon Apr 18 '16 at 13:31

2 Answers2

2

For Inductive Hypothesis:

LHS: $\sum_{j=0}^{k+1}(4j-1)=(4*1-1)+(4*2-1)+ ... +(4*(k-1)-1)+(4*k-1)+(4*(k+1)-1)=k(2k+1)+(4*(k+1)-1)=2k^2+k+4k+3=2k^2+5k+3$

RHS: $(k+1)(2(k+1)+1)=(k+1)(2k+3)=2k^2+5k+3$

$\therefore$ LHS=RHS

Brian
  • 205
2

Induction hypothesis (IH): For all $x\leq k$, assume $$\sum_{j=1}^x (4j-1) = x(2x+1)$$ in particular, $$\sum_{j=1}^k (4j-1)=k(2k+1)$$

Then \begin{align} \sum_{j=1}^{k+1} (4j-1) &= \left(\sum_{j=1}^k (4j-1)\right) + (4(k+1)-1)\\ &= k(2k+1) + 4(k+1)-1 \quad\quad (IH)\\ &= k(2k+1)+4k+3\\ &= 2k^2+5k+3\\ &= k(2k+3)+2k+3\\ &= (k+1)(2k+3)\\ &= (k+1)(2(k+1)+1) \end{align}

As in the comments, your error was in writing $4k+1-1$ instead of $4(k+1)-1 = 4k+3$. The rest is algebra/arithmetic.

Proof without requiring induction: $$\sum_{j=1}^k (4j-1) = \frac{4k(k+1)}{2}-k=2k(k+1)-k=2k^2+k=k(2k+1)$$

Nicholas Stull
  • 3,014