# Thread: Recursive definition and induction

1. ## 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.

2. ## Re: Recursive definition and induction

Originally Posted by CStudent
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!

3. ## Re: Recursive definition and induction

Originally Posted by Plato
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

4. ## Re: Recursive definition and induction

Originally Posted by Plato
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.
Originally Posted by romsek
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.

5. ## Re: Recursive definition and induction

Originally Posted by CStudent
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.

6. ## Re: Recursive definition and induction

Originally Posted by romsek
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.

7. ## Re: Recursive definition and induction

Originally Posted by CStudent
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.

8. ## 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

9. ## 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.