What is the inductive step for proving mathematical induction?

[racket]

Hey!

I've just started to learn some mathematical induction and it's proving quite tricky. Hopefully someone could help me out a little with my questions!

I don't know how to format question on this forum but I'll try my best to accurately represent it:

n
\(\displaystyle sigma\) i * 2^i = (n-1) * (2^n+1) + 2
i=1

Now, I know that I have to prove for the base case, which I take it to be 0. If I do so, it holds true however I don't know what the meaning of i=1 under the sigma represents. Does that mean the base case must equal 1? If so it doesn't work out I think.

If anyone could help me figure out this one problem, that'd be awesome!

Thank you!

 

[Prove It]

Is this what you are trying to prove?

$$\displaystyle \begin{align*} \sum_{i = 1}^n{\left( i \cdot 2^i \right) } = \left( n -1 \right)\, 2^{n + 1} + 2 \end{align*}$$

 

[racket]

Yes that's exactly what I'm trying to prove, thanks for formatting it for me!

 

[zzephod]

Hey!

I've just started to learn some mathematical induction and it's proving quite tricky. Hopefully someone could help me out a little with my questions!

I don't know how to format question on this forum but I'll try my best to accurately represent it:

n
\(\displaystyle sigma\) i * 2^i = (n-1) * (2^n+1) + 2
i=1

Now, I know that I have to prove for the base case, which I take it to be 0. If I do so, it holds true however I don't know what the meaning of i=1 under the sigma represents. Does that mean the base case must equal 1? If so it doesn't work out I think.

If anyone could help me figure out this one problem, that'd be awesome!

Thank you!

If you take \(\displaystyle n=0\) as the base case the sum on the left hand side is an empty sum and so equal to zero, as is the right hand side. Which will work as a base case. However you will probably be better off using \(\displaystyle n=1\) as your base case and avoid the degenerate sum you get when \(\displaystyle n=0\).

Using \(\displaystyle n=1\) as a base case you will, when you have proven the inductive step, have proven the result for every \(\displaystyle n\ge 1\), taking \(\displaystyle n=0\) as a base case you will when you have proven the inductive step have proven the result for every \(\displaystyle n\ge 0\)

.

 

[racket]

When I do that with the base case as 1 I get:

1 * 2^1 = (1 -1) * (2^n+1) + 2

2 = 2

Okay so, here's my work so far:

I'm assuming n = m when m >= 1

So n + 1.

And (m - 1) * (2^m+1) + 2 = m(2^m+2) + 2

Now I'm stuck but am I on the right track?

 

[chisigma]

Hey!

I've just started to learn some mathematical induction and it's proving quite tricky. Hopefully someone could help me out a little with my questions!

I don't know how to format question on this forum but I'll try my best to accurately represent it:

n
\(\displaystyle sigma\) i * 2^i = (n-1) * (2^n+1) + 2
i=1

Now, I know that I have to prove for the base case, which I take it to be 0. If I do so, it holds true however I don't know what the meaning of i=1 under the sigma represents. Does that mean the base case must equal 1? If so it doesn't work out I think.

If anyone could help me figure out this one problem, that'd be awesome!

Thank you!

A general formula for...

$\displaystyle S_{n} = \sum_{k=1}^{n} k\ x^{k}\ (1)$

... can be found as follows. You start from the well known...

$\displaystyle g(x)= \sum_{k=0}^{n} x^{k} = \frac{1 - x^{n+1}}{1 - x}\ (2)$

... and from (2) You derive...

$\displaystyle S_{n} = x\ \frac{d}{d x} g(x) = \frac{x}{(1 - x)^{2}} - (n-1)\ \frac{x^{n+1}}{1 - x}\ (3)$

Of course for x=2 You obtain...

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

... and of course all that doesn't use mathematical induction... Kind regards $\chi$ $\sigma$

 

[MarkFL]

After having shown the base case $P_1$ is true, I would next state the induction hypothesis $P_k$:

\(\displaystyle \sum_{i=1}^k\left( i\cdot2^i \right)=(k-1)2^{k+1}+2\)

As the inductive step, try adding \(\displaystyle (k+1)2^{k+1}\) to both sides. You want to be able to arrange the result as $P_{k+1}$:

\(\displaystyle \sum_{i=1}^{k+1}\left( i\cdot2^i \right)=((k+1)-1)2^{(k+1)+1}+2\)

Once you've done this, then your proof by induction will be complete.

 

[racket]

Once I've done that, would I get:

k(2^k+2) + 2

On the right side?

How do I complete the proof from this point?

 

[MarkFL]

Once I've done that, would I get:

k(2^k+2) + 2

On the right side?

How do I complete the proof from this point?

No, your right side becomes:

\(\displaystyle (k-1)2^{k+1}+2+(k+1)2^{k+1}\)

Now, see if you can show that this is:

\(\displaystyle ((k+1)-1)2^{(k+1)+1}+2\)

 

[racket]

Ah I'm sorry this is still confusing to me. Why exactly do you add (k+1)2^k+1 to both sides? On the left side do you change the i's to k's ?

 

[MarkFL]

Ah I'm sorry this is still confusing to me. Why exactly do you add (k+1)2^k+1 to both sides? On the left side do you change the i's to k's ?

Using the inductive step I gave immediately makes the left side what it needs to be. Consider:

\(\displaystyle \sum_{k=a}^n\left(f(k) \right)+f(n+1)=\sum_{k=a}^{n+1}\left(f(k) \right)\)

And no, there is no need to change the index of summation.

 

[racket]

I get it! Thank you, it's early and for some reason I didn't see it. Do you mind explaining one more thing? Why exactly does the inductive step make the left side what it's needed to be? Is that the same for all questions like this one?

 

[MarkFL]

I get it! Thank you, it's early and for some reason I didn't see it. Do you mind explaining one more thing? Why exactly does the inductive step make the left side what it's needed to be? Is that the same for all questions like this one?

Usually, if the left side of the induction hypothesis is a sum, then adding what would be the next term to both sides is a good inductive step. If the left side is a product, the you would want to multiply both sides by what would be the next term.

In many cases, you want to look at the left side and consider what you can do to it to make it what you need. This will be your inductive step. After demonstrating the base case is true, you then state the induction hypothesis $P_k$. Then, you want to use legal algebraic operations to derive from this $P_{k+1}$.