Proof via Induction for A Summation

Question

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically:

$$ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $$

Any hints would be greatly appreciate

Answer 1

Base case:

• Let $n=1$ and test: $$\sum_{i=1}^1(3i-2)=3-2=1=\frac{1(3\cdot 1-1)}{2}$$

• True for $n = 1$

Induction Hypothesis:

• Assume that it is true for $k$: assume that $$\sum_{i=1}^k(3i-2)=\frac{k(3k-1)}{2}.$$

Inductive Step:

• Prove, using the Inductive Hypothesis as a premise, that $$\sum_{i=1}^{k+1}(3i-2)=\left(\sum_{i = 1}^k(3i - 2)\right) + (3(k+1)-2) = \frac{(k+1)(3(k+1)-1)}{2}.$$

Answer 2

For $n=1$ you have $\sum_{i=1}^1(3i-2)=3-2=1=\frac{1(3\cdot 1-1)}{2}$.

Suppose that $$\sum_{i=1}^n(3i-2)=\frac{n(3n-1)}{2}$$ and prove that $$\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3(n+1)-1)}{2}.$$

Answer 3

Let's try amWhy's proof for a general summation:

$$ \sum_{i=1}^n f(i) = g(n)$$

Base case:

• Let $n=1$ and test: $$\sum_{i=1}^1 f(i) = f(1) =?\ g(1)$$

• True for $\,n = 1\iff \color{#C00}{f(1) = g(1)}$

Induction Hypothesis:

• Assume that it is true for $\, n = k$: assume that $$\sum_{i=1}^k f(i) = g(k).$$

Inductive Step:

• Prove, using the Induction Hypothesis as a premise, that $$\sum_{i=1}^{k+1}f(i)=\left(\sum_{i=1}^k f(i)\right) + f(k\!+\!1) = g(k) + f(k\!+\!1) =?\ g(k\!+\!1).$$

• Inductive step from $k$ to $k+1$ is true $\iff \color{#C00}{ g(k\!+\!1) - g(k) = f(k\!+\!1)}$

Therefore we have proved by induction the following generic summation criterion

Theorem $\displaystyle\,\ \sum_{i=1}^n f(i) = g(n)\iff g(1) = f(1)\ {\rm and}\ g(n\!+\!1)-g(n) = f(n\!+\!1)\ $ for $\,n \ge 1.$

Indeed, the induction proves the direction $(\Leftarrow),$ and $(\Rightarrow)$ is clear.

This theorem reduces the inductive proof to simply verifying the RHS equalities, which is trivial polynomial arithmetic when $f(n),g(n)$ are polynomials in $n$. The above theorem is an example of telescopy, also known as the Fundamental Theorem of Difference Calculus, depending on context. You can find many more examples of telescopy and related results in other answers here.

Answer 4

hint:we know that $$\sum_{"i=1}^ni=\frac{n(n+1)}{2}$$ then write $\sum_{i=1}^n(3i-2)$=$3\sum_{i=1}^n(i) -2n$ substitute above assumption $\sum_{i=1}^n (3i-2 )= \frac{n(3n-1)}{2}$

Answer 5

I will prove it in two way for you:

1- Mathematical Induction:

If $n=1$ then the left side is $1$ and also the right side is $1$ too.

Now think that we have $\sum_{i=1}^{n}(3i-2)=\frac{n(3n-1)}{2}$, we should show $\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3(n+1)-1)}{2}$ that is $\sum_{i=1}^{n+1}(3i-2)=\frac{(n+1)(3n+2)}{2}$. But we can write; $$\sum_{i=1}^{n+1}(3i-2)=(\sum_{i=1}^{n}(3i-2))+(3(n+1)-2)=\frac{n(3n-1)}{2}+(3n+1)=\frac{3n^{2}-n+6n+2}{2}=\frac{3n^{2}+5n+2}{2}=\frac{3n^{2}+3n+2n+2}{2}=\frac{3n(n+1)+2(n+1)}{2}=\frac{(n+1)(3n+2)}{2}$$. And it finished our work.

2- Without Mathematical Induction:

We know $\sum_{i=1}^{k}i=\frac{k(k+1)}{2}$ and $\sum_{i=1}^{k}c=kc$ for a constant number "c".

Now $$\sum_{i=1}^{n}(3i-2)=3\sum_{i=1}^{n}i-\sum_{i=1}^{n}2=3\frac{n(n+1)}{2}-2n=\frac{n(3n+3-4)}{2}=\frac{n(3n-1)}{2}$$.