# Induction over propositional variables

I have the formula: $A_n = \bigvee^{n-1}_{i=0}( X_i \oplus X_{i+1} )$ Now I have to transform it to an equivalent formula with only $\neg , \vee$ and $\wedge$. Then I have to prove it with induction. So i transformed it to: $A_n = \bigvee^{n-1}_{i=0}( \neg X_i \wedge X_{i+1} )\vee(X_i \wedge \neg X_{i+1})$. Hope that's ok so far. Then in the induction basis I thought I could prove with solving the value table, (which worked). But is that correct to solve it about that? And in the induction step I don't know how to sum up the formula: (btw. I'll induce over $n-1$ to $n$ not from $n$ to $n+1$).
$(\neg X_{n-1} \wedge X_n) \vee (X_{n-1}\wedge X_n) \bigvee_{i=0}^{n-2}(\neg X_{i} \wedge X_{i+1}) \vee (X_{i}\wedge X_{i+1})$ = by the induction hypothesis: $(\neg X_{n-1} \wedge X_n) \vee (X_{n-1}\wedge X_n)\bigvee_{i=0}^{n-2}X_{i} \oplus X_{i+1}$

...?

Thanks for help!

It's very straightforward. The base case ($n=1$) is just $$X_0 \oplus X_1 \iff (X_0 \wedge \neg X_1) \vee (\neg X_0 \wedge X_1)\tag{Eq_1}$$ You can establish this by any means at your disposal: truth tables, a derivation, definitions and equivalences you already know and can appeal to, etc.
Induction Hypothesis (IH): Assume $$\bigvee^{n-1}_{i=0}( X_i \oplus X_{i+1} ) \iff \bigvee^{n-1}_{i=0}((X_i \wedge \neg X_{i+1}) \vee (\neg X_i \wedge X_{i+1})) \tag{Eq_n}$$ Using the identity $$X_n \oplus X_{n+1} \iff (X_n \wedge \neg X_{n+1}) \vee (\neg X_n \wedge X_{n+1}) \text{,}\tag{Id}$$ "or"ing the LHS and RHS of (Id) onto the LHS and RHS of ($Eq_n$) respectively, gives the desired result, with the "big vee" index $i$ ranging from $0$ to $n$.