Mathematical Induction Help

racket

New member
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

Well-known member
MHB Math Helper
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

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

zzephod

Well-known member
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

New member
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

Well-known member
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

Staff member
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

New member
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

Staff member
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?

$$\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

New member
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

Staff member
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

New member
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

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}$.