Structural induction proof

144 Views Asked by At

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?