(Solved): We examine a series of propositional formulas \( F_{1}, F_{2} \ldots . . F_{n} \ldots \)... contain ...

We examine a series of propositional formulas \( F_{1}, F_{2} \ldots . . F_{n} \ldots \)... containing propo- "mes" - 2018/6/6 - 13:43 - page 163 - 4171 53. Sorving induction on Induction vs. Well Oniering sitional variables \( P_{1}, P_{2} \ldots ., P_{n} \ldots \). constructed as follows \( F_{5}\left(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right) \) Let \( T_{n} \) be the number of different true/false settings of the variables \( P_{1}, P_{2} \ldots \ldots P_{n} \) for which the statement \( F_{n}\left(P_{1}, P_{2} \ldots \ldots P_{n}\right) \) is true. For example, \( T_{2}=3 \) since \( F_{2}\left(P_{1}, P_{2}\right) \) is true for 3 different settings of the variables \( P_{1} \) and \( P_{2} \) : (a) Explain why \[ T_{n+1}=2^{n+1}-T_{n} . \] (b) Use induction to prove that \[ T_{n}=\frac{2^{n+1}+(-1)^{n}}{3} \] for \( n \geq 1 \).