Welcome to our community

Be a part of something great, join today!

Mathematical Induction Help

racket

New member
Nov 28, 2013
6
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
Jan 26, 2012
1,403
Is this what you are trying to prove?

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

racket

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

zzephod

Well-known member
Feb 3, 2013
134
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
Nov 28, 2013
6
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
Feb 13, 2012
1,704
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Nov 28, 2013
6
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

Administrator
Staff member
Feb 24, 2012
13,775
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

New member
Nov 28, 2013
6
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Nov 28, 2013
6
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

Administrator
Staff member
Feb 24, 2012
13,775
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}$.