# Recursive definition and induction

• MHB
• CStudent
In summary, the series $a_n$ is defined by a recursive formula $a_n = a_{n-1} + a_{n-3}$. Every natural number can be written as a sum (of one or more) of different elements of the series. However, proving this is not an easy task, as there is a problem with powers of 3.f

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

Thanks.

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.
Since you're unclear on the concept of recursion, it would be a good idea to calculate a few terms of the sequence. (Note that what you have here is a sequence of numbers. A series is the sum of numbers in some sequence.)

From the given info we have:
##a_1 = 1##
##a_2 = 2##
##a_3 = 3##
Using the recursion formula, we get:
##a_4 = a_3 + a_1 = 3 + 1 = 4##
##a_5 = a_4 + a_2 = 4 + 2 = 6##
##a_6 = a_5 + a_3 = 6 + 3 = 9##
and so on...

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.
It's not a really easy proof, I think.

- How would you go about writing a natural number as a sum of the elements of a sequence. I think there's a rather obvious algorithm.
- What can go wrong with this algorithm. Why does it fail with powers of 3.
- How can you prove that this can't happen here. (using the recursion)

• Greg Bernhardt