Would an induction approach work here?

I used induction. I think I got a 7 on this one.

Use strong induction.

v_Enhance wrote: Use strong induction. the reverse of the first several letters of $X_{n-1}$ In facts, that is X_n-2 I think?

v_Enhance wrote: Use strong induction.

Yeah that's what I did except my conclusion part was more than a little bit sketchy -.-

Quote: This middle part, the last few chars of X_n are the first few characters of X_n by inductive hypothesis. Then use Fibanocci identities to show that this is equivalent to X_{n-3} and you're done. Why is that first part true?

I proved about 4 statements, one of which is that every W will start with either ab or ba, and the rest will be a palindrome.

Ditto with Ancheyo. Only problem is, rather then doing them empirically, I sort of worked backwards (I started with the hardest statement, then proved successive reductions of the problem). Ended up with about 3 nested inductions, lol. The proof should be valid, I just hope they don't get mad that it gets side-windy.

I thought this was quite simple, compared to everything else on day 2: Induction!

Could anyone tell me if this solution works? So basically I wrote that since each string W_n where n>=1 has F_n (the nth fibonacci number) of letters. And since i didn't know how to prove that F_1+F_2+...+F_n=F_(n+2)-2, I wrote, "It is well-known that..." I used induction to assume that the string up to W_k was a palindrome, so W_(k-1) and W_(k) repeat the first F_(k+1) letters. therefore W_(k+1) would also repeat F_(k+1) letters and have F_(k+1) letters itself, for a total of 2*F_(k+1). but then i messed up and said that there were F_(k+2)-2 letters in the string because i forgot to replace K with K+1... and I ended up saying that 2*F_(k+1)>F_(k+2)-2 so the number was a palindrome. would I get any points for that?

benjamin7xx wrote: $S_{k+1} = S_{k-2}W_{k-1}W_kW_{k-1}W_k$ Take the $S_{k-1}W_{k-1}W_k$ part and reverse it, since we used induction we know that S_k is a palindrome, so reversing that part is still the same. After reversing it, obviously S_{k+1} is a palindrome. Why can you reverse $S_{k-1}W_{k-1}W_k$?

Here's my solution. I think it's right. Sorry, I've forgotten how to use LaTeX. Don't think I actually ever lerned it Notation: S_k = W_1W_2W_3...W_k all strung together. F_k = length of W_k (F because of Fibonacci) L_k = length of S_k Strong Induction: Base case: Works for S_1 through S_4 (b, bab, babbab, babbababbab) Inductive step: Assume S_n-2, S_n-1, S_n are all palindromes (here, I think I might not have needed S_(-1 but included it for good measure) To get S_(+1 we append the last F_n+1 letters of S_n to S_n itself. But since S_n is symmetric about its center letter(s) we can instead take the first F_n+1 letters and append them in reverse order, and still get the same result. Then we notice that the first L_n - F_n letters are a palindrome since that's just S_n-2, which is assumed. Again by symmetry that's also the last L_n-F_n letters, but order doesn't matter (we're assuming symmetry). That's the middle terms. Therefore S_n+1 is a palindrome since its middle is a palindrome, and its letters on either side are reflections of each other. QED IMHO this one compared to the others is almost trivial.

exmath89 wrote: benjamin7xx wrote: $S_{k+1} = S_{k-2}W_{k-1}W_kW_{k-1}W_k$ Take the $S_{k-1}W_{k-1}W_k$ part and reverse it, since we used induction we know that S_k is a palindrome, so reversing that part is still the same. After reversing it, obviously S_{k+1} is a palindrome. Why can you reverse $S_{k-1}W_{k-1}W_k$? Sorry typo, meant to say $S_{k-2}W_{k-1}W_k$.

Let $S_n$ denote the word obtained when the word $W_n$ is written backwards. The first few words $W_n$ and $S_n$ are as follows: \[ \begin{array}{c|l|l} n & W_n & S_n \\ \hline 0 & a & a \\ 1 & b & b \\ 2 & ab & ba \\ 3 & bab & bab \\ 4 & abbab & babba \\ 5 & bababbab & babbabab \\ 6 & abbabbababbab & babbababbabba \end{array} \] Since $W_n = W_{n - 2} W_{n - 1}$ (which denotes the concatenation of $W_{n - 2}$ and $W_{n - 1}$) for all $n \ge 2$, $S_n = S_{n - 1} S_{n - 2}$ for all $n \ge 2$. When we write the word $W_1 W_2 \dotsb W_n$ backwards, we obtain $S_n S_{n - 1} \dotsb S_1$. We claim that \[W_1 W_2 \dotsb W_n = S_n S_{n - 1} \dotsb S_1\] for all $n \ge 1$, which proves that $W_1 W_2 \dotsb W_n$ is a palindrome. We prove this using strong induction. The claim is true for $n = 1$. Assume there exists a positive integer $k$ so that the claim is true for all $n = 1$, 2, $\dots$, $k$. In other words, \[W_1 W_2 \dotsb W_n = S_n S_{n - 1} \dotsb S_1\] for all $1 \le n \le k$. Consider the word $W_1 W_2 \dotsb W_k W_{k + 1}$. By the induction hypothesis, $W_1 W_2 \dotsb W_k = S_k S_{k - 1} \dotsb S_1$, so \[W_1 W_2 \dotsb W_k W_{k + 1} = S_k S_{k - 1} S_{k - 2} \dotsb S_1 W_{k + 1}.\] Since $S_k S_{k - 1} = S_{k + 1}$ and $W_{k + 1} = W_{k - 1} W_k$, \[S_k S_{k - 1} S_{k - 2} \dotsb S_1 W_{k + 1} = S_{k + 1} S_{k - 2} \dotsb S_1 W_{k - 1} W_k.\] By the induction hypothesis, $S_{k - 2} S_{k - 3} \dotsb S_1 = W_1 W_2 \dotsb W_{k - 2}$, so \[S_{k + 1} S_{k - 2} \dotsb S_1 W_{k - 1} W_k = S_{k + 1} W_1 W_2 \dotsb W_{k - 2} W_{k - 1} W_k.\] By the induction hypothesis, $W_1 W_2 \dotsb W_k = S_k S_{k - 1} \dotsb S_1$, so \[S_{k + 1} W_1 W_2 \dotsb W_{k - 2} W_{k - 1} W_k = S_{k + 1} S_k \dotsb S_1.\] Hence, \[W_1 W_2 \dotsb W_{k + 1} = S_{k + 1} S_k \dotsb S_1.\] The claim holds for $n = k + 1$, and by induction, for all positive integers $n$.

Personally, I thought this was the easiest problem this year. I did it a little differently though.

Nsato, that was just what I did (literally almost line by line, except I used $ W'_{n} $ instead of $ S_{n} $). I thought it was a bit sketchy at first, but I'm glad that it works.

Could somebody please check my solution?

Thanks so much! I wish I could've found something as elegant as nsato's proof, but whatever.

I have a different method...

Notice that if we let $f = ab$ then assuming $W_1W_2 \cdots W_n$ is a palindrome implies that $W_2W_3 \cdots W_{n+1}$ is a palindrome in $f$ and $b$. But now we can apply a reduction algorithm on $bW_2W_3 \cdots W_{n+1}$ to show that it is a palindrome in $a$ and $b$. In particular, $bf$[palidrome in $f$, $b$]$f \rightarrow b$ [palidrome in $f$, $b$], and $bb$ [palidrome in $f$, $b$] $b \rightarrow b$ [palidrome in $f$, $b$] (where we continually erase the same letters from both ends). So at the end we will be left with $b$, $bf$, or $bb$, all of which are palindromes.

Nice problem! For a word $W$, let $\overline{W}$ denote the word spelled in reverse: remark that $\overline{W_{n+1}} = \overline{W_{n}} \overline{W_{n-1}}.$ Now we proceed with strong induction. Suppose that the inductive hypothesis holds for all positive integers up to $n$; note that $$W_1W_2 \dots W_{n+1} = \overline{W_n } \overline{W_{n-1}} \dots \overline{W_1} W_{n+1} = \overline{W_{n+1}}\overline{W_{n-2}} \overline{W_{n-3}} \dots \overline{W_{1}}W_{n+1} = \overline{W_{n+1}} W_1W_2 \dots W_{n-2} W_{n+1}.$$But this last expression is equal to $\overline{W_{n+1}}W_1W_2 \dots W_{n-2} (W_{n-1} W_n) = \overline{W_{n+1} W_n\dots W_1},$ which shows that $W_1W_2 \dots W_{n+1}$ is a palindrome.

Hard for a JMO 1/4. Lot's of ways to attack the problem that just don't work. Induct on $n \ge 4$, base cases easy. Note that the length of $W_n$ is the Fibonacci number $F_{n+1}$. Denote $\overline{X}$ as the reverse of the word $X$. We know $W_1\cdots W_{n-2}W_{n-1}$ is a palindrome. Hence the first $F_{n+1}$ letters of $W_1\cdots W_{n-1}$ spell out $\overline{W_{n-1}} \ \overline{W_{n-2}} = \overline{W_n}$. Hence \[ W_1\cdots W_n = (W_1\cdots W_{n-1})(W_n) = \overline{W_n} S W_n, \]where $\overline{W_n}S = W_1\cdots W_{n-1}$. So it suffices to show that $S$ is a palindrome. We calculate the length of $S$: \[ \ell(S) = F_2+\cdots+F_n - F_{n+1} = (F_{n+2}-2)-F_{n+1} = F_n-2. \]Since $\ell(W_{n-1}) = F_n$, in fact $S$ is $W_{n-1}$ with the first 2 letters chopped off. Hence, we have reduced the problem to the following claim purely about $W_n$: Claim: For any $n\ge 2$, if we chop off the first 2 letters of $W_n$, the result is a palindrome. Proof: We will prove it for $n\ge 4$, base cases easy. It is easy to see (by induction) that $W_{2k} = ab\ldots ab$ and $W_{2k-1}=ba\ldots ab$. So it suffices to show that \[ W_{2k}ba, \quad \text{and} \quad W_{2k-1}ab\]are palindromes. We will prove this statement by induction on $k$, base cases easy to verify. Notice \[ W_{2k}ba = W_{2k-2}W_{2k-1}ba = W_{2k-2}W_{2k-3}W_{2k-2}ba. \]It's reverse is hence \[ ab \overline{W_{2k-2}} \ \overline{W_{2k-3}} \ \overline{W_{2k-2}} = (ab) (\overline{W_{2k-2}}-ba)(ba)(\overline{W_{2k-3}}-ab)(ab)(\overline{W_{2k-2}}). \]By induction, $W_{2k-2}ba$ is a palindrome, so $(ab)(\overline{W_{2k-2}}-ba)=W_{2k-2}$. By induction, $W_{2k-3}ab$ is a palindrome, so $(ba)(\overline{W_{2k-3}}-ab) = W_{2k-3}$. By induction, $W_{2k-2}ba$ is a palindrome, so $W_{2k-2}ba = ab\overline{W_{2k-2}}$. We have matched up every piece to a piece of the reverse, so we've proved $W_{2k}ba$ is a palindrome. A similar argument (which would need to be written out in test) can be used to prove $W_{2k-1}ab$ is a palindrome. The idea is to expand down three levels of $W$, and then write the reverse, and match up every piece to the reverse -- we know they must be equal, so this matching up is easy (but tedious) to check. This finishes the induction, and the problem. $\blacksquare$

wait this is cute Strong induct (base case obvious); let $\overline{A}$ denote the reverse of a word $A$. Then noting $\overline{AB}=\overline{B} \ \overline{A}$,$$\overline{W_1 \cdots W_{n}}=\overline{W_n} \ \overline{W_1 \cdots W_{n-1}}=\overline{W_n}W_1 \cdots W_{n-3}W_{n-2}W_{n-1}=\overline{W_n}W_1 \cdots W_{n-3}W_n$$where the last word is a palindrome.

Because we want to prove it for any integer $n \ge 1$ we think of using induction! Define $S_n$ to be the concatenation of $W_1, W_2, W_3, \dots, W_n$. Now the base cases are trivial, so lets move onto the inductive step. We assume that $S_{n-1}$ is a palindrome and now we have the inductive step. We have\begin{align*} S_k&=S_{k-1}W_k \\ &=S_{k-3}W_{k-2}W_{k-1}W_{k-2}W_{k-1} \end{align*}Now because we have $S_{k-1}$ is a palindrome, reversing $S_{k-3}W_{k-2}W_{k-1}$ will lead to $S_k$ being a palindrome.

@above can you explain the last line? What do you mean by reversing $S_{k-3}W_{k-2}W_{k-1}$ will lead to $S_k$ being a palindrome? This solution seems much shorter than the other solutions.

OlympusHero wrote: @above can you explain the last line? What do you mean by reversing $S_{k-3}W_{k-2}W_{k-1}$ will lead to $S_k$ being a palindrome? This solution seems much shorter than the other solutions. Sure! Maybe I should've been more clear but anyways, notice that $S_{k-1}=S_{k-3}W_{k-2}W_{k-1}$. Then let $\overline{S}$ for some word $S$ denote the reverse of the word. Since we know (by our inductive hypothesis) $S_{k-3}$ and $S_{k-1}$ are palindromes as well, we know $S_{k-1}=\overline{W_{k-2}W_{k-1}}S_{k-3}$ so $S_k=\overline{W_{k-2}W_{k-1}}S_{k-3}W_{k-2}W_{k-1}$ which is obviously a palindrome, as desired.

Let us use strong induction, if $S(k)$ = assertion that $W_{1}.....W_{k}$ is a palindrome, $S(1)$ and $S(2)$ are true. Assume that for any postitive integer from $1$ through $k$ has the property that $S(k)$ is true, then let us show $W_{1}.....W_{k+1}$ is a palindrome. By the induction hypothesis $S(k)$ is true, hence by the word reads the same as $W_{k}W_{k-1}.....W_{1}W_{k+1}$ now we write $W(k+1)$ as $W_{k-1}$ followed by $W_{k}$ it reads now as $W_{k}W_{k-1}W_{k-2}.......W_{1}W_{k-1}W_{k}$ again, by the induction hypothesis $S(k-2)$ is true hence the resulting word is a palindrome hence $S(k + 1)$ is also true and the proof is complete

Let $\overline{A}$ denote the reverse of word $A$. Note that $\overline{A+B}=\overline{B}+\overline{A}$, where $+$ denotes concatenation. We employ strong induction, with base cases being manually verifiable. Now, for the inductive step, we have \begin{align*} \overline{W_1+\cdots+W_n}&=\overline{W_n}+\overline{W_1+\cdots+W_{n-1}}\\ &=\overline{W_n}+W_1+\cdots+W_{n-1}\\ &=(\overline{W_{n-2}+W_{n-1}})+W_1+\cdots+W_{n-3}+(W_{n-2}+W_{n-1}), \end{align*}where the second equality comes from the inductive hypothesis applied to $n-1$ and the second comes from our definition of $W_n$. Because $W_1+\cdots+W_{n-3}$ is a palindrome by inductive hypothesis (again), it is clear that $\overline{A}+W_1+\cdots+W_{n-3}+A$ is a palindrome for any word $A$, hence $\overline{W_1+\cdots+W_n}$ is a palindrome, and so is $W_1+\cdots+W_n$ as desired. $\blacksquare$

Define the binary operation $+$ on strings so that $S_1 + S_2$ is the result of writing $S_1$ followed by $S_2$, and let $r(S)$ denote the reverse of the string $S$. Now, let $X_n =W_1 + W_2 + \dots + W_n$ for all $n\ge 1$. We will prove the desired via strong induction. We can take $n = 1,2,3$ as base cases. Now, assuming the result holds for all $k\le n$ for fixed $n\ge 3$, we have \begin{align*} r(X_{n+1}) &= r(W_{n+1}) + r(X_n)\\ &= r(W_{n-1} + W_n) + X_n\\ &= W_n + W_{n-1} + X_n\\ &= W_n + W_{n-1} +X_{n-2} + W_{n-1} + W_n\\ &= r(W_n + W_{n-1} +X_{n-2} + W_{n-1} + W_n),\\ \end{align*}so $X_{n+1} = W_n + W_{n-1} + X_{n-2} + W_{n-1} + W_n$. Hence, it suffices to show that $W_n + W_{n-1} + X_{n-2} + W_{n-1} + W_n$ is a palindrome. To do this, it suffices to show that $X_{n-2}$ is a palindrome, but this is true from the inductive hypothesis. This completes the induction, so we are done.

We note the following: The first two letters of $W_i$ alternate between $ab$ and $ba$. The length is $W_i$ is the $i$-th Fibonacci number. $F_{n+2}-2 = F_1 + F_2 + \ldots + F_n$, so the letters of $W_1, W_2, \ldots, W_{n-2}$ along with the $ab$ or $ba$ prefix of $W_{n-1}$ correspond with the letters of $W_n$. Thus we can use strong induction to show the following statements, which finishes the proof: The first $F_n$ letters are in fact the reverse of $W_n$. Each word without its first 2 letters is a palindrome. $\blacksquare$

Very refreshing We let $\overline W$ denote the word $W$ written backward. Note that $\overline{AB} = \overline B \ \overline A$. Now we strong induct on $n$: notice that \begin{align*} X_n &= \left(\overline {X_{n-1}}\right) W_n \\ &= \left(\overline {W_{n-1}}\ \overline {W_{n-2}} \cdots \overline{W_1}\right) W_n \\ &= \overline {W_n }\left(\overline {W_{n-3}} \ \overline {W_{n-2}} \cdots \overline{W_1}\right) W_n \\ &= \overline {W_n} X_{n-3} W_n. \end{align*}As $X_{n-3}$ is a palindrome, $X_n$ must be a palindrome too.

Denote $\overline{W}$ as the reversed version of the word $W$. Moreover, let $+$ denote concatenation. We employ induction, with the base cases $W_1 = b$, $W_1 + W_2 = bab$, and $W_1+W_2+W_3 = babbab$ all being palindromes, as desired. Then, note that \begin{align*} \overline{W_1+W_2+ \dots + W_n} &= \overline{W_n} + \overline{W_1+W_2+\dots+W_{n-1}} \\ &=\overline{W_n} + (W_1+W_2+\dots+W_{n-1}) \\ &= \overline{W_{n-2}+W_{n-1}}+ (W_1+W_2+\dots+W_{n-3}) + (W_{n-2}+W_{n-1}), \end{align*} which is a palindrome due to our inductive hypothesis, thus implying that $W_1+W_2+ \dots + W_n$ is a palindrome as well. $\blacksquare$