Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By Plato

Thread: Recursive definition and induction

  1. #1
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Recursive definition and induction

    Hey.

    The series $a_n$ is defined by a recursive formula $a_n = a_(n-1) + a_(n-3)$ and its base case is $a_1 = 1 \ a_2 = 2 \ a_3 = 3$.
    Prove that every natural number can be written as a sum (of one or more) of different elements of the series $a_n$.

    Now, I know that is correct intuitively but I don't know how to prove that.
    Generally, I have some problem of understanding the concept of recursion.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3048
    Awards
    1

    Re: Recursive definition and induction

    Quote Originally Posted by CStudent View Post
    Hey.
    The series $a_n$ is defined by a recursive formula $a_n = a_{n-1} + a_{n-3}$ and its base case is $a_1 = 1 \ a_2 = 2 \ a_3 = 3$.
    Prove that every natural number can be written as a sum (of one or more) of different elements of the series $a_n$.
    Now, I know that is correct intuitively but I don't know how to prove that.
    Generally, I have some problem of understanding the concept of recursion.
    As you can see I fixed the subscripts using {} \$a_n = a_{n-1} + a_{n-3}\$ Any time you have a superscript or subscript with more than one character in it enclose the whole superscript or subscript in braces.

    Please review the post for mistakes. You post $a_n = a_{n-1} + \color{red}{a_{n-3}}$ and its base case is $a_1 = 1 \ a_2 = 2 \ a_3 = 3$ Is that correct?
    Because that means $a_4=4,a_5=6,a_6=9,a_7=13,a_8=19,a_9=28,a_{10}=41$ There is nothing wrong with the recursion. But it does not go with this phrase "every natural number can be written as a sum (of one or more) of different elements of the series $a_n$"

    Maybe you can give a clearer explanation of what it means? Please do!
    Thanks from CStudent
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,363
    Thanks
    2734

    Re: Recursive definition and induction

    Quote Originally Posted by Plato View Post
    As you can see I fixed the subscripts using {} \$a_n = a_{n-1} + a_{n-3}\$ Any time you have a superscript or subscript with more than one character in it enclose the whole superscript or subscript in braces.

    Please review the post for mistakes. You post $a_n = a_{n-1} + \color{red}{a_{n-3}}$ and its base case is $a_1 = 1 \ a_2 = 2 \ a_3 = 3$ Is that correct?
    Because that means $a_4=4,a_5=6,a_6=9,a_7=13,a_8=19,a_9=28,a_{10}=41$ There is nothing wrong with the recursion. But it does not go with this phrase "every natural number can be written as a sum (of one or more) of different elements of the series $a_n$"

    Maybe you can give a clearer explanation of what it means? Please do!
    he means the recursion generates a sequence $S=\{s_n\}$

    and that $\forall k \in \mathbb{N},~ \exists \{s_m\} \subset S \ni \sum s_m = k$

    think of the sequence as a sort of basis for $\mathbb{N}$ but restricted to binary coefficients
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Recursive definition and induction

    Quote Originally Posted by Plato View Post
    As you can see I fixed the subscripts using {} \$a_n = a_{n-1} + a_{n-3}\$ Any time you have a superscript or subscript with more than one character in it enclose the whole superscript or subscript in braces.

    Please review the post for mistakes. You post $a_n = a_{n-1} + \color{red}{a_{n-3}}$ and its base case is $a_1 = 1 \ a_2 = 2 \ a_3 = 3$ Is that correct?
    Because that means $a_4=4,a_5=6,a_6=9,a_7=13,a_8=19,a_9=28,a_{10}=41$ There is nothing wrong with the recursion. But it does not go with this phrase "every natural number can be written as a sum (of one or more) of different elements of the series $a_n$"

    Maybe you can give a clearer explanation of what it means? Please do!
    That's exactly the way the question is given...

    Thank for the repairs.
    Quote Originally Posted by romsek View Post
    he means the recursion generates a sequence $S=\{s_n\}$

    and that $\forall k \in \mathbb{N},~ \exists \{s_m\} \subset S \ni \sum s_m = k$

    think of the sequence as a sort of basis for $\mathbb{N}$ but restricted to binary coefficients
    I didn't actually understand what to do with your suggestion...
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,363
    Thanks
    2734

    Re: Recursive definition and induction

    Quote Originally Posted by CStudent View Post
    That's exactly the way the question is given...

    Thank for the repairs.


    I didn't actually understand what to do with your suggestion...
    Thanks.
    There's no suggestion there. I'm just explaining to Plato, and anyone else, what your question means.

    I looked at the problem. It's not too hard to see that you can make up any natural number as a combination of the sequence members
    but I can't prove it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2018
    From
    France
    Posts
    40

    Re: Recursive definition and induction

    Quote Originally Posted by romsek View Post
    There's no suggestion there. I'm just explaining to Plato, and anyone else, what your question means.

    I looked at the problem. It's not too hard to see that you can make up any natural number as a combination of the sequence members
    but I can't prove it.
    Weird...
    I have heard there is some technique to prove it by using the property of a monotonic increasing series.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3048
    Awards
    1

    Re: Recursive definition and induction

    Quote Originally Posted by CStudent View Post
    I have heard there is some technique to prove it by using the property of a monotonic increasing series.
    The post's title is " Recursive definition and induction"
    Even if romsek were correct in his reading, since the sequence contains $1$ we can generate the naturals.
    But why induction? The sequence $a_n$ (it is a sequence not a series) is clearly monotonic increasing. But what does that to do with anything?
    Being a sequence of naturals it cannot be bounded above & convergence is out the question.
    As we see here the recurrence as no solution. Thus I have no idea what a proposition for induction could be.

    The reason I asked the question that did was it really $a_n=a_{n-1}+a_{n-2}$ we see here that there is a solution in terms Fibonacci & Lucas numbers.
    Now it possible to use induction.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    907
    Thanks
    434

    Re: Recursive definition and induction

    use induction on $m$

    If $\displaystyle a_n < m < a_{n+1}$ for some natural number $n$

    then $\displaystyle m-a_n$ is less than $m$ so it can be written as the sum of distinct elements of the sequence, say

    $\displaystyle m-a_n=b_1 + b_2 + ... + b_k$ with $\displaystyle b_1<b_2<...<b_k$

    show that $\displaystyle b_k<a_n$

    and $\displaystyle m =b_1 + b_2 + ... + b_k+a_n$ is a sum of distinct elements
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,363
    Thanks
    2734

    Re: Recursive definition and induction

    I don't want to get into arguments about the precise wording of things.

    It seems pretty clear that the recursion and initial conditions produce a sequence of positive integers

    $A = \{1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595,872, 1278, 1873 \dots \}$

    Now let's look at the missing integers

    $5 = 4+1$

    $7=6+1$

    $8 = 6+2$

    $10 = 9+1$

    $11=9+2$

    $12=9+3$
    .
    .
    .
    $87 = 60 + 19 + 6 + 2$

    etc.

    the problem is to prove such a summation always exists as the gaps in $A$ get larger and larger

    coming up with an algorithm to derive the subset of A whose sum equals n would do it.
    Last edited by romsek; Dec 2nd 2018 at 10:45 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive Definition
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Oct 9th 2011, 05:33 AM
  2. recursive definition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 21st 2008, 10:51 PM
  3. What is the recursive definition for 1 + (-1)^n?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 6th 2008, 06:45 PM
  4. Recursive definition??
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 30th 2008, 03:37 AM
  5. Recursive Definition
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 22nd 2007, 06:55 AM

/mathhelpforum @mathhelpforum