Vrftsjtryk

$$S_{n} = sum_{i=0}^{n}(5i+3)$$

I received a homework problem that instructed me to use induction to prove that for all natural numbers n

$$S_{n} = frac{n(5n+11)}{2}+3$$

First I proved that my base case of $S_{0}$ holds, because substituting $0$ for $n$ in both the top formula and the following formula makes both equal to $3$. The next step is to form my inductive hypothesis. My hypothesis is that

$$sum_{i=0}^{n}(5i+3) = frac{n(5n+11)}{2}+3$$ for all natural numbers $n$. Then I'm assuming that $$sum_{i=0}^{k}(5i+3) = frac{k(5k+11)}{2}+3$$ holds when $n$ = some arbitrary natural number $k$ (I've since been told not to do $n=k$ for some reason).

Next step is to prove that $S_{k+1}$ holds, because if it does, knowing that my base case holds will tell me that $S_{1}$ holds, telling me that $S_{2}$ holds, etc.

To prove this, I took the equation from my assumption and substituted $k+1$ for $k$. Evaluating the left hand side of $frac{(k+1)(5(k+1)+11)}{2}+3$ eventually yielded $frac{5k^2+21k+22}{2}$, and solving the right hand side of $sum_{i=0}^{k+1}(5i+3)$ using Gauss's(?) sum and splitting the terms of the sum (I don't know what to call it) to come to the same result. Since both sides of the equation reduced to the same expression, I reasoned that this proves that my original assumption holds, therefore the statement at the top has been proven.

I've gone wrong somewhere above, since I was told that I proved the original assertion with a direct proof rather than by induction. Where did I go wrong? I thought that after making my assumption and learning the case that needs to hold to make such assumption true, all I need to do is see if both sides of the equation equal each other. Has doing a direct proof of the original statement caused me to make too many assumptions? Or have I done something else inappropriate?

Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.

So our assumption is

$$sum_{i=0}^{k}(5i+3) = frac{k(5k+11)}{2}+3$$

We seek to show

$$sum_{i=0}^{k+1}(5i+3) = frac{(k+1)(5(k+1)+11)}{2}+3 = frac{(k+1)(5k+16)}{2}+3$$

Starting with the sum at the left, we can pull out the $(k+1)^{th}$ term:

$$sum_{i=0}^{k+1}(5i+3) = 5(k+1) + 3 + sum_{i=0}^{k}(5i+3) = 5k+8 + sum_{i=0}^{k}(5i+3)$$

As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:

$$begin{align}
5k+9 + sum_{i=0}^{k}(5i+3) &= 5k+8 + frac{k(5k+11)}{2}+3\
&=frac{10k+16 + 5k^2 + 11k}{2} + 3\
&=frac{5k^2+21k+16}{2} + 3\
&= frac{(k+1)(5k+16)}{2}+3
end{align}$$

Thus, the case for $(k+1)$ holds, completing the induction step.

I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".

What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.

As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.