# Structural induction proof

I am trying to solve the following problem, please help me to complete the proof:

I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of f functional symbols and the number $p_g$ of g functional symbols in term $t$ .

$f$ is an unary func symbol, $g$ is ternary one.

My induction assumption is that this relation is $p_c(t) = 2p_g(t) +0p_f(t)$, where $p_g$ and $p_c$ show num of corresponding symbols in the term $t$ respectively.

Having this, base:

$p_c(x)=0$, where $x$ is some variable. Assumption holds

Step:

let $k_i \in \{k_a, k_b, k_c\}$ are some terms. $p_c(k_i) = 2p_g(k_i)$

Then $p_c(k_{i+1}) = p_c(f(k_i)) = 0 + 2 p_g(k_i)$ or

$p_c(k_{i+1}) = p_c(g(k_a, k_b, k_c)) = 2 + p_c(k_a)+ p_c(k_b)+ p_c(k_c) = 2 + 2p_g(k_a)+ 2p_g(k_b)+ 2p_g(k_c)$

what should I write next?

• Better late than never ... – Bram28 Nov 8 '16 at 18:34

Beforehand, I would state the claim that you are trying to prove simply as $p_c(t) = 2p_g(t)$
First say that you need to show $p_c(k_{i+1}) = 2p_g(k_{i+1})$
In the case where $k_{i+1} = f(k_i)$, the number of g functional symbols in $k_{i+1}$ equals the number of g functional symbols in $k_i$, and so $p_c(k_{i+1}) = p_c(k_i) = 2p_g(k_i) = 2p_g(k_{i+1})$
In the case where $k_{i+1} = g(k_a, k_b, k_c)$, the number of g functional symbols in $k_{i+1}$ is 1 + all the g functional symbols in the other terms, i.e. $p_g(k_{i+1}) = p_g(k_a) + p_g(k_b) + p_g(k_c) + 1$. So then: $p_c(k_{i+1}) = p_c(k_a) + p_c(k_b) + p_c(k_c) + 2 =$ (by inductive hypothesis) $= 2p_g(k_a) + 2p_g(k_b) + 2p_g(k_c) + 2 = 2(p_g(k_a) + p_g(k_b) + p_g(k_c) + 1) = 2p_g(k_{i+1})$
So yes, in both cases $p_c(k_{i+1}) = 2p_g(k_{i+1})$