Results 1 to 4 of 4

Thread: proof by induction

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    proof by induction

    prove by induction that 4^n-1 is divisible by three for all posotive integers of n
    any help would be appriciated thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    Initialization of induction is easy.

    Let's suppose that for a given n $\displaystyle 4^{n}-1$ is divisible by 3.
    You need to demonstrate that $\displaystyle 4^{n+1}-1$ is divisible by 3.
    Hint : $\displaystyle 4^{n+1}-1 = 4(4^{n}-1)+3$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    16,216
    Thanks
    3701
    prove $\displaystyle 4^n - 1$ is divisible by 3

    true for $\displaystyle n = 1$

    assume true for $\displaystyle n$, show true for $\displaystyle (n+1)$ ...

    since $\displaystyle 4^n - 1$ is divisible by 3, then $\displaystyle 4^n - 1 = 3k$ , $\displaystyle k$ a positive integer.

    $\displaystyle 4^n - 1 = 3k$

    $\displaystyle 4(4^n - 1) = 4(3k)$

    $\displaystyle 4^{n+1} - 4 = 12k$

    $\displaystyle 4^{n+1} - 1 - 3 = 12k$

    $\displaystyle 4^{n+1} - 1 = 12k + 3$

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

    since $\displaystyle (4k+1)$ is also a positive integer, $\displaystyle 4^{n+1} - 1$ is a multiple of 3, and therefore, is divisible by 3.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, hmmmm!

    Here's another way . . .


    Prove by induction that $\displaystyle 3|(4^n-1)$ for all positive integers $\displaystyle n.$

    Verify $\displaystyle S(1)\!:\;\;4^1-1 \:=\:3$ . . . true

    Assume $\displaystyle S(k)\!:\;\;4^k-1 \:=\:3a\,\text{ for some integer }a.$


    Add $\displaystyle 3\!\cdot\!4^k$ to both sides: .$\displaystyle {\color{blue}3\!\cdot\!4^k} + 4^k - 1 \;=\;3a + {\color{blue}3\!\cdot\!4^k}$


    Factor: .$\displaystyle (3 + 1)4^k - 1 \;=\;3\left(a + 4^k\right)$

    . . . . . . . . $\displaystyle 4\!\cdot4^k - 1 \;=\;3\left(a + 4^k\right)$

    . . . . . . . . $\displaystyle 4^{k+1}-1 \;=\;\underbrace{3\left(a + r^k\right)}_{\text{a multiple of 3}}$


    We have proved $\displaystyle S(k+1)$ . . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum