- Prove with induction that |w^n| = n · |w|.
Ive tried to prove this statement with induction but am having trouble finishing it.
I think the base case is: n = 0
|w^0| = ε(empty word) because w^0 = zero copies of w and 0 · |w| = ε
Here are some important definitions:
Exponentiation of words : w^i = i copies of w concatenated together concatenation of words : let w = abc and w' = ccc. then ww' = abcccc. ww' ≠ w'w
computing length of words : |ax| = 1 + |x| if w = ax where a ∈ Σ and x ∈ Σ* -------- |abc| = 1 + |bc| = 1 + 1 + |c| = 1 + 1 + 1 + |ε| = 1 + 1 + 1 + 0 = 3
first prove that if $|wv| = |w| + |v|$ by doing induction on $|w| = n$.
Base case: If $|w| = 1$ then $w = a$ for some character $a$ and $wv = av$ and $|av| = 1 + |v|$.
Induction: If $|w'v| = |w'| + |v|$ for all $|w'| \le n$ and if $|w|= n+1$ then $w = aw'$ for some character $a$ and so some word $w':|w'|=n$.
So $|wv| = |a(w'v)| = 1 + |w'v| =1+(n+|v|)= (n+1) + |v| = |w| +|v|$.
.....
Okay. Now then
your proof. $|w^n| = n|w|$.
Base case: $|w^1| = |w|$
Induction. If $|w^n| = n*|w|$ then $|w^{n+1}|= |ww^{n}| =|w| + |w^n|=|w| + n*|w| = (n+1)*|w|$.