2

When doing an induction problem is it wrong to simply add the next variable to both sides? for example

for all natural numbers

$$4+9+14+19....+(5n-1)=\frac{n}{2}(3+5n)$$

assume true for k

$$4+9+14+19....+(5k-1)=\frac{k}{2}(3+5k)$$

is it wrong to do this

$$4+9+14+19...+(5k-1)+(5k+4)=\frac{k}{2}(3+5k)+(5k+4)$$

or

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

assume true for $k$

$$3+3(5)+3(5)^2...+3(5)^k=\frac{3(5^{k+1}-1)}{4}$$

$$3+3(5)+3(5)^2...+3(5)^k+3(5)^{k+1}=\frac{3(5^{n+1}-1)}{4}+3(5)^{k+1}$$

Brian Fitzpatrick
  • 26,559
user128922
  • 113
  • If you're doing something to both side... Why would it be wrong? ā€“ Shahar Mar 10 '14 at 23:26
  • 2
    You still need a base case of course, but apart from that, this is a very useful technique to use when proving something using induction! ā€“ Ragnar Mar 10 '14 at 23:31

2 Answers2

5

It is not wrong at all. And I'm afraid I will have to disagree with the answer above by @Sanath Devalapurkar since it is very much a justified and useful tool in proving something using induction.

Note that you have "used" the fact that the statement given to you is true for $k$ and then made an attempt to prove it for $k + 1$ which is perfectly fine. If you can simplify the right hand sides of those two equations to show that they are equal to $\dfrac {k +1 }{2} (3 + 5 (k + 1))$ and $\dfrac {3(5^{k + 2} - 1)}{4}$ then you would have completed "one of the two" tasks stipulated by the Principle of Mathematical Induction.

You must also prove a base case - typically show hat the statements are true when $n = 1$. If you complete both these tasks you would have proven the results are true for every natural number $n$.

I stress again that your method is a very valid in the process of proving a result using induction.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
0

Yes, this is perfectly valid. In order to do what you're trying do accomplish here with induction, what you would do is assume it holds, like you have, for some k $\ge$ 1, i.e, $$\sum_{n=1}^k (5nāˆ’1) = \frac k2(3+5k)$$

Now you can simply add $5(k+1)-1=5k+4$ to both sides of the equation, just like you have, to get

$$\sum_{n=1}^{k+1} (5nāˆ’1) = \frac k2(3+5k)+5k+4$$

Now is the time to take your logic one step further. We simply do a little algebra on the terms of the right side of the equation to get

$$\begin{align} \frac k2(3+5k)+5k+4 &=\frac k2(3+5k)+\frac 12(10k+8) \\ & =\frac {k(3+5k)+10k+8}2 \\ & =\frac {15k^2+13k+8}2 \\ & =\frac {k+1}2(5k+8) \\ & =\frac {k+1}2(3+5k+5) \\ & =\frac {k+1}2(3+5(k+1)) \end{align}$$ Which is exactly what we wanted to show.

So what we've done is shown that if the statement is true for some positive integer k, then it must also be true for k+1. Now we have to establish our base case, namely, that the statement is true for k=1. This is quite simple, really: $$5(1)-1=4$$ $$\frac {(1)}2(3+5(1))=\frac 82=4$$ So, since we have shown that if the statement holds for one number, it must hold for the next, and since it does hold for n=1, it must also hold for n=2, which means it must also hold for n=3, which means it must also hold for n=4... and so the logic chains on to infinity. This means that it must hold for all n$\epsilon\mathbb{N}$, the set of natural numbers. This completes our proof by induction, and you may now write, in your most elaborate cursive, $\mathscr{Q.E.D.}$

P.S. I want to apologize if I may have made the process look more complicated than it is with all these steps. I just wanted to guide you step-by-step through the process of completing a proof by induction. It's really not that hard, it just requires a little abstract thinking.

silvascientist
  • 4,087