MaBloWriMo 7: s via omega

Yesterday, I challenged you to prove that

$s_m = \omega^{2^m} + \overline{\omega}^{2^m} \pmod{M_n}$

where $\omega = 2 + \sqrt{3}$ , $\overline{\omega} = 2 - \sqrt{3}$ , and the $s_m$ are defined by $s_0 = 4$ and $s_n = (s_{n-1}^2 - 2) \bmod M_n$ .

The proof is by induction on $m$ . The base case $m = 0$ is just arithmetic:

$\omega^{2^0} + \overline{\omega}^{2^0} = \omega^1 + \overline{\omega}^1 = (2 + \sqrt 3) + (2 - \sqrt 3) = 4 = s_0.$

Now suppose that we already know the statement holds for some particular $m \geq 0$ ; we must show that it also holds for $m+1$ . The proof is not too hard, but we have to handle the stacked exponents with care! (Note also that all the following equalities are really taken $\pmod M_n$ , which is OK since addition, subtraction, and multiplication are all compatible with taking remainders.)

$\begin{array}{rcl} s_m^2 &=& \left(\omega^{2^m} + \overline{\omega}^{2^m}\right)^2 \\[5pt] &=& \left(\omega^{2^m}\right)^2 + 2\omega^{2^m} \overline{\omega}^{2^m} + \left(\overline{\omega}^{2^m}\right)^2 \\[5pt] &=& \omega^{2^{m+1}} + 2(\omega \overline{\omega})^{2^m} + \overline{\omega}^{2^{m+1}} \\[5pt] &=& \omega^{2^{m+1}} + \overline{\omega}^{2^{m+1}} + 2\end{array}$

(The last step is because we know from yesterday that $\omega \overline{\omega} = 1$ .) So $\omega^{2^{m+1}} + \overline{\omega}^{2^{m+1}} = s_m^2 - 2 = s_{m+1} \pmod M_n$ , which is what we wanted to show.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

11 Responses to MaBloWriMo 7: s via omega

sinuheancelmo says:

November 8, 2015 at 9:43 pm

Here it is proved not only the equality mod M_n, but it is also proved the equality in general. Am I right?
- Brent says:
  
  November 9, 2015 at 1:21 pm
  
  Well, we defined the s_n in terms of mod M_n in the first place. I will write more about this today.
  - sinuheancelmo says:
    
    November 9, 2015 at 2:13 pm
    
    Ok. Thanks.
sinuheancelmo says:

November 8, 2015 at 11:23 pm

Hendrix College is a University or a high-school? What can we study there, high-school subjects or universitary careers?
- Brent says:
  
  November 9, 2015 at 1:25 pm
  
  The terminology can be confusing since it is used very differently depending on what country you are in. Hendrix is definitely not a high school, it is a 4-year school that a student would attend after completing high school. It is not a university though, the difference being that it is relatively small and does not offer graduate degrees like a master’s degree or PhD.
  - sinuheancelmo says:
    
    November 9, 2015 at 2:14 pm
    
    Ok, thanks for your answer, friend!
Pingback: MaBloWriMo 8: definition of s and mod | The Math Less Traveled
sinuheancelmo says:

November 9, 2015 at 2:16 pm

So, here are studied professional careers, but with a duration of 4 years. What careers are studied here, for instance?
- Brent says:
  
  November 9, 2015 at 2:18 pm
  
  I suggest you just go poke around https://www.hendrix.edu/ , I think you will be able to find answers to your questions much more quickly that way than I would be able to answer them. For example there is a list of the academic programs here: https://www.hendrix.edu/academics/majorsandminors/
  - sinuheancelmo says:
    
    November 9, 2015 at 2:24 pm
    
    Thank you!
    
    I had visited that site, but I hadn’t reviewed the academics section.
Pingback: MaBloWriMo 21: the order of omega, part I | The Math Less Traveled

Comments are closed.