2
$\begingroup$

Here is a question I've been working on and so far, can't get anything.

Suppose we have a string which is recursively defined as:

base case: A = F

recursive case: ( A N A )

such as a string X = ( ( F N ( F N F ) ) N ( ( ( F N F ) N F) N (F N F ) ) )

We have two functions used to calculate the amount of characters in the string. First, the function $f(a) = \left\{ \begin{array}{ll} 1 &\text{if }a=F;\\ f(a_1)+f(a_2) &\text{if }a=a_1\>N\>a_2. \end{array}\right.$ calculates the amounts of 'F' in the string.

Second, the function: $g(a) = \left\{ \begin{array}{ll} 1 &\text{if }a=F;\\ f(a_1)+1+f(a_2) &\text{if }a=a_1\>N\>a_2. \end{array}\right.$

I need to prove by induction that $g(a) \leq 2f(a) + 1$.

I've tried drawing trees of the string, finding a pattern in various strings generated by the recursive definition and I really cant seem to be able to find anything.

Thanks for your help.

  • 0
    Indeed ! Sorry, I've been working on this all day long, brain is a bit slushy.2011-04-18

1 Answers 1

3

Your $f$ counts the number of $F$s in the string. I think that your $g$ is meant to be the length, and that the formula should be: $g(A) = \left\{\begin{array}{ll} 1 &\text{if }A=F;\\ g(a_1)+g(a_2)+1 &\text{if }A=a_1\>N\>a_2 \end{array}\right.$

I claim that $g(A)\leq 2f(A)-1$. This will also imply your inequality.

First, we show that the inequality holds for the base case: it does, since $g(F) = 1$, $f(F) = 1$, so $g(F)\leq 2f(F)-1$ holds.

For the inductive step, assume that the result holds for a particular string $A$; that is, $g(A) \leq 2f(A)-1$. You want to show that the result will also hold for the "next string"; the next string is A N A. So you want to compare $f(\text{A N A})$ with $g(\text{A N A})$.

By definition, $f(\text{A N A}) = f(A)+f(A) = 2f(A)$. On the other hand, $g(\text{A N A}) = g(A)+1+g(A).$ By the induction hypothesis, $g(A)\leq 2f(A)-1$, so $\begin{align*} g(\text{A N A}) &= g(A)+1+g(A)\\ &\leq 2f(A)-1 + 1 + 2f(A)-1\\ &= 2f(A)+2f(A) -1\\ &= f(\text{A N A}) + f(\text{A N A}) -1\\ &= 2f(\text{A N A}) -1. \end{align*}$ So this shows that if $g(A)\leq 2f(A)-1$, then $g(\text{A N A})\leq 2f(\text{A N A})-1$ will also hold.

By induction, it holds for all the strings that we generate starting with $F$ and following the given rule.

If you really did want $g(A) \leq 2f(A)+1$, then since $2f(A)-1\leq 2f(A)+1$, it will follow from this.

If your definition for $g$ was correct, then the result also follows: it holds for $A=F$ by direct computation, and if $g(\text{A})\leq 2f(\text{A})+1$, then since $f(\text{A N A}) = 2f(A)$, we have: $g(\text{A N A}) = f(A)+f(A)+1 = 2f(A)+1 =f(\text{A N A})+1 \leq 2f(\text{A N A})+1$ since $f(a)\geq 0$ for all $a$, so the desired inequality holds.

  • 0
    Wow, thanks for the quick and extremely clear answer. I could not have asked for more !2011-04-18