1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Do you understand the meaning of the first problem, "give an expression for $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$" ? $\endgroup$ Commented Aug 19, 2018 at 12:37
  • $\begingroup$ (I've edited most of your question to format the mathematical formulae using Latex. I left the last paragraph though. If you hit "edit" under your question, you'll be able to see the Latex code I used. Could you please take a look and format the formulae in the last paragraph, just to learn how it works?) $\endgroup$ Commented Aug 19, 2018 at 12:42
  • $\begingroup$ @JackM I think I edited it. I think also, I got the understanding of the first problem wrong. I thought it was to find a general expression for a(n) by using a(n-1) and a(n-2)? Am I right? $\endgroup$ Commented Aug 19, 2018 at 13:00
  • $\begingroup$ I'm pretty sure I've seen this very question posted recently, but it seems to have been deleted. $\endgroup$ Commented Aug 19, 2018 at 13:10
  • 1
    $\begingroup$ You seem to be trying to do part 2 of the exercise without doing in part 1 first. That will not work; the result of part 1 will be used in part 2. $\endgroup$ Commented Aug 19, 2018 at 13:21

2 Answers 2

Reset to default
1
$\begingroup$

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}$

$\endgroup$
2
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.