I am having trouble to understand the way of using a induction for the following example:
Let $\Sigma \overset{\Delta} = \{a, b\}$ and $S_1 \overset{\Delta} = \{a^n \mid n \in \Bbb N\}$. Prove using induction that $$\forall w \in \Sigma^* . w \in S_1 \to \big( w = \lambda \lor (\forall \ 1 \le i \le |w| . (w)_i = a) \big) .$$
How to do that? Any help is upvoted.
Induction on the lenght $n$ of the string.
i) $n=1$ : then $|w|=1$. But also $w=a$, by definition of $S_1$, and thus $(w)_1=a$.
ii) $n \to n+1$ : then $|w|=n+1$. But also $w=w'a$, where $|w'|=n$.
By induction hypotheses : $(w)_i=(w')_i=a$, for $1 \le i \le n$ and also $(w)_{n+1}=a$, and thus :
As already commented by others, the use of induction here is quite "excessive".
We rely on the fact that, by definition of $S_1= \{a^n \mid n \in \mathbb N \}$, $(w)_i=a$, for any $i \le |w|$.
Thus, we already have the result, i.e.