1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Find a recurrence relation for this problem

  1. Sep 28, 2010 #1
    1. The problem statement, all variables and given/known data
    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.]

    3. The attempt at a solution
    No idea.
  2. jcsd
  3. Sep 28, 2010 #2


    Staff: Mentor

    Re: Recurrence

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook