ดูต้นฉบับสำหรับ 418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 8

ในการแก้ปัญหาข้อนี้เราจะให้ <math>\Sigma \,</math> แทนเซตของ'''พยัญชนะ'''ทั้งหมดที่เป็นไปได้ เช่น ถ้าสตริงที่เราสนใจเกิดจากการนำพยัญชนะของภาษาอังกฤษมาประกอบกัน เราอาจจะให้ <math>\Sigma = \{ \mathrm{a, b, c, \ldots, z} \} \,</math> เป็นต้น

นอกจากนี้ เพื่อให้ไม่ให้เกิดความสับสน เราจะแทนสตริงด้วยตัวอักษรภาษาอังกฤษตัวเล็ก เช่น <math>x, y, z \,</math> เป็นต้น และจะแทนตัวอักษรด้วยตัวอักษรกรีก เช่น <math>\alpha, \beta, \gamma \,</math> เป็นต้น

== ข้อย่อย 1 ==
ให้ <math>x \,</math> เป็นสตริง เรานิยามสตริงกลับ <math>x^R \,</math> ของ <math>x \,</math> ดังต่อไปนี้
: <math>x^R = 
\begin{cases}
\lambda, & x = \lambda \\
y^R \alpha, & x = \alpha y
\end{cases}
</math>
เมื่อ <math>y \,</math> เป็นสตริงและ <math>\alpha \in \Sigma \,</math> เป็นพยัญชนะ

== ข้อย่อย 2 ==
ให้ <math>P \,</math> เป็นเซตของสตริงที่เป็นพาลินโดรม เราสามารถนิยาม <math>P \,</math>  ได้จากกฎต่อไปนี้
* <math>\lambda \in P</math>
* ถ้า <math>\alpha \in \Sigma</math> แล้ว <math>\alpha \in P</math>
* ถ้า <math>\alpha \in \Sigma</math> และ <math>x \in P</math> แล้ว <math>\alpha x \alpha \in P</math>

== ข้อย่อย 3 ==
ในปัญหาข้อนี้ ให้ <math>n \,</math> แทนความยาวของสตริง <math>x \,</math> (ความยาวของสตริงคือจำนวนตัวอักษรในสตริงนั้น)

เราจะพิสูจน์ข้อความ <math>(xy)^R = y^R x^R</math> โดยใช้ induction บนตัวแปร <math>n \,</math>

(Base Case) <math>n = 0\,</math> เราจะได้ว่า <math>x = \lambda \,</math> ฉะนั้น <math>(xy)^R = (\lambda y)^R = y^R = y^R \lambda^R = y^R x^R \,</math>

(Induction Case) ให้ <math>n \,</math> เป็นจำนวนเต็มที่ไม่เป็นลบ และสมมติว่าสำหรับสตริง <math>z \,</math> ที่มีความยาว <math>n \,</math> ใดๆ <math>(zy)^R = y^R z^R \,</math>

ให้ <math>x \,</math> เป็นสตริืงที่มีความ <math>n+1 \,</math> ใดๆ สมมติให้ <math>x = \alpha z \,</math> โดย <math>\alpha \in \Sigma \,</math>

เราได้ว่า <math>(xy)^R = (\alpha zy)^R = (zy)^R \alpha = y^R z^R \alpha = y^R x^R \,</math>

ดังนั้นเราสามารถสรุปได้ว่า <math>(xy)^R = y^R x^R \,</math> สำหรับสตริง <math>x \,</math> และ <math>y \,</math> ใดๆ