Results 1 to 8 of 8
Like Tree3Thanks
  • 1 Post By HallsofIvy
  • 1 Post By HallsofIvy
  • 1 Post By JeffM

Thread: Prove by induction that for every positive integer n

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Prove by induction that for every positive integer n

    Sum $\sum_{i=1}^{n} 2^{i} = 2^{n+1} -2 $


    Could Anyone please give me an Idea of how I would go about solving this problem .?

    Any advice would be appreciated cheers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,457
    Thanks
    2892

    Re: Prove by induction that for every positive integer n

    The problem says "by induction". Can we assume you know what that means?

    First, of course, when n= 1, \sum_{i=1}^n 2^i= 2^1= 2 while 2^{n+1}- 2 is 2^2- 2= 4- 2= 2. So the statement is true when n= 1.

    Now suppose the statement is true for n= k, say. That is, suppose \sum_{i=1}^k= 2^{k+1}- 2. Then \sum_{i=1}^{k+1} 2^i is just the same sum with one additional term: \sum_{i=1}^{k+1} 2^i= \left(\sum_{i= 1}^k 2^i\right)+ 2^{k+1}. Replace that \sum_{i=1}^k 2^i with 2^k- 2 and do the algebra.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Re: Prove by induction that for every positive integer n

    Thanks HallsofIvy,
    Induction means a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.
    Do I simply just sub in 1 for k into 2^k -2 which you have written after the last summation?
    making it equal to 2 -2 = 0? and compare it with the earlier summation
    I'm kinda not sure how to do the second part with the k+1 power added and break it down from there ....

    Sum $\sum_{i=1}^{k+1} 2^{i}$ =( Sum $\sum_{i=1}^{k+1} 2^{i}$)+2^k+1 replacing that Sum $\sum_{i=1}^{k} 2^{i}$ with 2^k - 2

    how you broke it down I'm a little confused with ....
    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Re: Prove by induction that for every positive integer n

    Thanks HallsofIvy,
    Induction means a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.
    Do I simply just sub in 1 for k into 2^k -2 which you have written after the last summation?
    making it equal to 2 -2 = 0? and compare it with the earlier summation
    I'm kinda not sure how to do the second part with the k+1 power added and break it down from there ....

    Sum $\sum_{i=1}^{k+1} 2^{i}$ =( Sum $\sum_{i=1}^{k+1} 2^{i}$)+2^k+1 replacing that Sum $\sum_{i=1}^{k} 2^{i}$ with 2^k - 2

    how you broke it down I'm a little confused with ....
    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,457
    Thanks
    2892

    Re: Prove by induction that for every positive integer n

    Well, there's your problem. You are asked to prove this "using proof by induction" and you do not know what induction is! You really need to talk to your teacher about this.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,750
    Thanks
    808

    Re: Prove by induction that for every positive integer n

    Quote Originally Posted by bee77 View Post
    Sum $\sum_{i=1}^{n} 2^{i} = 2^{n+1} -2 $


    Could Anyone please give me an Idea of how I would go about solving this problem .?

    Any advice would be appreciated cheers.
    Let's approach this three ways. We want to prove that P(n) is true for every natural number.

    The formal approach. Let S be the set for which every element s is a natural number such that P(s) is true. But S may be empty. So prove P(1) is true. Thus S is not empty. Let k be ANY element of S (there is at least one element in S). Because k in S, P(k) is true. So we we know that 1, k, and k + 1 are all natural numbers and that P(1) and P(k) are true. Using those five facts prove P(k+1) is true. Thus k + 1 in S. Therefore S = N.

    That is the formal structure of a proof by weak mathematical induction.

    The intuitive approach. If something is true for 1 and for the next number past a number for which that something is true, then it is true for 1, but it is also true for 1 + 1, the number next after 1 or 2, which makes it true for the number next after 2, or 3, which makes it true for 4 and then 5 and so on forever. The intuition is of an infinite number of dominoes falling.

    The practical approach. The n = 1 step is usually easy. The challenge arises on the k to k + 1 step. There probably is no general way to attack all proofs by induction, but a very common practical approach when you are asked to equate two expressions is to form your expression in k + 1 and expand it into an expression involving k and known numbers without any mention of (k + 1).

    $\displaystyle \text {PROVE: } n \in \mathbb N^+ \implies \sum_{j=1}^{n} 2^{j} = 2^{(n+1)} - 2.$

    First, prove for n = 1.

    $\displaystyle n = 1 \implies \sum_{j=1}^{n} 2^{j} = \sum_{j=1}^{1} 2^{j} =$

    $2^1 = 2 = 4 - 2 = 2^2 - 2 = 2^{(1+1)} - 2 = 2^{(n+1)} - 2.$

    That was easy enough.

    Second step.

    $\displaystyle \text {LET: } k \text { be any number such that } k \in \mathbb N^+ \text { and } \sum_{j=1}^{k} 2^{j} = 2^{(k+1)} - 2.$

    We can say that because we know that there is at least one such number, namely 1, but we are not assuming that k = 1.

    OK before we actually try to do the proof, let's be sure to grasp what are we trying to do. We want to prove that

    $\displaystyle \sum_{j=1}^{k+1} 2^{j} = 2^{\{(k+1)+1\}} - 2.$

    Let's expand the first expression into something that does not involve (k + 1) at all.

    $\displaystyle \sum_{j=1}^{k+1} 2^{j} = \left ( \sum_{j=1}^k 2^{j} \right ) + 2^{(k+1)} = \left ( \sum_{j=1}^k 2^{j} \right ) + (2 * 2^k).$

    That was not so hard, was it?

    $\text {BUT} \displaystyle \sum_{j=1}^{k} 2^{j} = 2^{(k+1)} - 2 = (2 * 2^k) - 2.$

    $\therefore \displaystyle \sum_{j=1}^{k+1} 2^{j} = \left ( \sum_{j=1}^k 2^{j} \right ) + (2 * 2^k) =$

    $(2 * 2^k) - 2 + (2 * 2^k) = (4 * 2^k) - 2 = (2^2 * 2^k) - 2 = 2^{(k+2)} - 2 = 2^{\{(k+1)+1\}} - 2.$

    Done.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Re: Prove by induction that for every positive integer n

    Ok Thanks HallsofIvy .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Re: Prove by induction that for every positive integer n

    Thanks Jeff.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: Jan 1st 2016, 08:14 AM
  2. Prove that there exists a positive integer n
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Oct 26th 2009, 06:44 PM
  3. Replies: 2
    Last Post: Feb 22nd 2009, 03:49 PM
  4. Replies: 2
    Last Post: Feb 5th 2009, 03:27 PM
  5. Replies: 2
    Last Post: Oct 14th 2007, 06:32 AM

/mathhelpforum @mathhelpforum