Recursive definition and induction

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

 

[Mark44]

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

 

[willem2]

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)