Find a recurrence relation for this problem

[johnsmiths]

Homework Statement

Suppose that a mathematical expression can only be formed by the following symbols: 0, 1,
2, …, 9, ×, +, /. Some examples are “0 + 9”; “2 + 2 × 8”; “1 / 5 + 6”. Let a_n be the the number of such mathematical expression of length n (e.g. “0 + 9” is considered of length 3). Find a recurrence relation for a_n and compute the closed form for a_n.
[Some clarification: We define a number as follows
- 0, 1, 2, …, 9 is a number
- If x is a number, then x0, x1, …, x9 is a number
We define a valid expression as follows
- E is a valid expression if E is a number
- If E, F are valid expressions, then E + F, E × F, E / F are also valid expressions.
For example: 1+50/4 is an expression of length 6, and 09×00/5 is an expression of length 7.]

The Attempt at a Solution

No idea.

 

[Mark44]

Homework Statement

Suppose that a mathematical expression can only be formed by the following symbols: 0, 1,
2, …, 9, ×, +, /. Some examples are “0 + 9”; “2 + 2 × 8”; “1 / 5 + 6”. Let a_n be the the number of such mathematical expression of length n (e.g. “0 + 9” is considered of length 3). Find a recurrence relation for a_n and compute the closed form for a_n.
[Some clarification: We define a number as follows
- 0, 1, 2, …, 9 is a number
- If x is a number, then x0, x1, …, x9 is a number
We define a valid expression as follows
- E is a valid expression if E is a number
- If E, F are valid expressions, then E + F, E × F, E / F are also valid expressions.
For example: 1+50/4 is an expression of length 6, and 09×00/5 is an expression of length 7.]

The Attempt at a Solution

No idea.

Before trying to come up with a closed form expression for a_n it might be helpful to figure out a₁, a₂, and a few more.

a₁ is pretty easy, since a valid expression of length 1 can only be a number with a single digit.
a₂ is almost as easy, since a valid expression of length 2 can only a number with two digits.

Continue along these lines and see what you can come up with.