Struggling with what proof to use?

Question

So this is a problem from my text book:

A transaction string is a string over the alphabet $\{0,1,2,3,4,5,6,7,8,9,+,-\}$ in which:

• the operations $+$, $-$ never occur consecutively, and
• the last symbol is not an operation.

In this exercise, we allow positive integers to start with $0$, for simplicity. Examples of transaction strings include: $000$, $-5$, $25+144-169$, $-1000-0+007$. Examples of strings that are not transaction strings include: $153+46+-44$, $64---46$, $+$, $99+$. The first two of these have two consecutive operations, while the last two end in an operation. We will prove an upper bound on the number of transaction strings of length $n$. Since our alphabet has size $12$, we have the naive upper bound $12^n$. But we will do better than that.

Let $a_n$ be the number of transaction strings of length $n$

Questions:

Give (with justification) an expression for an in terms of $a_{n−1}$ and $a_{n−2}$, that works for all $n\geq 3$.

Prove, by induction on $n$, that $a_n \leq 11.8^n$ for all $n$.

--

So I'm a bit confused on how to do this question. I've found what $a_n$ is when n is equal to $1, 2, 3$ but I'm not sure if that helps with with question. With the inductive step, I'm not sure what proof to use here as I am confused on if I should be using proof by contradiction here? Can someone please point me in the right direction? Thanks

Answer 1

To answer this question you must first get the recurrence relation. In this case I would draw the different configurations you can get in terms of number(N) verses symbol(S). I found myself doing $a_3$, $a_4$ and $a_5$ helped for getting this recurrence. So for $a_4$ we can have

• NNNN
• NSNN
• NNSN

Do this for $a_3$ and $a_5$ and you should see a pattern.

From there the induction step is checking the base case $n=3$. The induction step can be done by looking at $a_{n+1}$, using the recurence relation found to get this in terms of $a_n$ and $a_{n-1}$. Then using the induction hypothesis $a_n <= (11.8)^n$ try to show $a_{n+1} <= (11.8)^{n+1}$

Answer 2

Let the first number in the expression be $n$. So your transaction string looks like $n + \dots$ or $n - \dots$

There are two cases:

1. If $n$ has one digit, so you have something like $9 + \dots$, etc.
2. If $n$ has more than one digit, so you have something like $99 + \dots$, etc

In each case, what's a simple algorithm to create a valid transaction string from shorter transaction strings? Can you turn that into a recurrence?

Once you have the recurrence, you'll want to use it to show that the solution for $a_n \leq 11.8^n$