Find a recurrence relation for this problem

In summary, the problem is to find a recurrence relation and closed form expression for the number of valid mathematical expressions of a given length, using the symbols 0-9, +, -, and /, with the given definitions of numbers and valid expressions. It is suggested to start by finding a1 and a2.
  • #1
johnsmiths
4
0

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 an 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 an and compute the closed form for an.
[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.
 
Physics news on Phys.org
  • #2


johnsmiths said:

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 an 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 an and compute the closed form for an.
[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 an it might be helpful to figure out a1, a2, and a few more.

a1 is pretty easy, since a valid expression of length 1 can only be a number with a single digit.
a2 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.
 

FAQ: Find a recurrence relation for this problem

1. What is a recurrence relation?

A recurrence relation is a mathematical relationship that defines a sequence or pattern in terms of its previous terms. It is typically used to recursively calculate the value of a sequence or function.

2. How do you find a recurrence relation for a problem?

To find a recurrence relation for a problem, you need to identify the pattern or relationship between the terms in the sequence. This can be done by examining the given data or by using algebraic manipulation to express the terms in terms of their previous terms. Once the pattern is identified, it can be written as a recursive formula.

3. Why is finding a recurrence relation important?

Finding a recurrence relation is important because it allows us to efficiently compute the value of a sequence or function without having to explicitly calculate each term. It also helps us understand the underlying pattern or relationship between the terms in a sequence, which can have applications in various fields of science and mathematics.

4. Are there different methods for finding a recurrence relation?

Yes, there are different methods for finding a recurrence relation. Some common techniques include using algebraic manipulation, using the method of differences, and using generating functions. The method used may vary depending on the complexity of the problem and personal preference.

5. Can a recurrence relation be used to solve real-world problems?

Yes, recurrence relations can be used to solve real-world problems. Many natural phenomena, such as population growth or compound interest, can be modeled using recurrence relations. They can also be used in computer science to analyze and optimize algorithms.

Similar threads

Back
Top