2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение24.07.2017, 22:54 


06/07/17
56
Задача: найти макс. степень двойки для $\left \lfloor (1+\sqrt{3})^{n} \right \rfloor$.

Если число n нечетное $\left \lfloor (1+\sqrt{3})^{n} \right \rfloor=(1+\sqrt{3})^{n}+(1-\sqrt{3})^{n}$, то получается выделить одну двойку,$2(1+\binom{n}{2}3+\binom{n}{4}3^{2}+...+\binom{n}{n-1}3^{\frac{n-1}{2}})$ остальные не знаю как. Если четное $\left \lfloor (1+\sqrt{3})^{n} \right \rfloor=(1+\sqrt{3})^{n}+(1-\sqrt{3})^{n}-1$ вообще на 2 не делится.

 Профиль  
                  
 
 Re: Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение25.07.2017, 03:10 
Заслуженный участник


12/07/07
4466
Долго пытался вспомнить решение, но так и не вспомнил. Но можно занудно, совсем очевидным способом.
Случай нечетного показателя. Обозначим его через $2k+1$.
$$(1+\sqrt 3)^{2k+1} + (1-\sqrt 3)^{2k+1} = (4+2\sqrt 3)^k(1+\sqrt 3) + (4-2\sqrt 3)^k(1-\sqrt 3) =$$ $$ = 2^k \left \{ \left [ (2+\sqrt 3)^k + (2-\sqrt 3)^k \right] + \left [ (2+\sqrt 3)^k - (2-\sqrt 3)^k \right] \sqrt3  \right \}.$$ Очевидно, что можно вынести 2 за фигурные скобки (т.е. «максимальная степень двойки» не меньше $k+1$). И надо показать, что выражение в фигурных скобках, после вынесения 2, уже больше не делится на 2.

 Профиль  
                  
 
 Re: Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение25.07.2017, 09:28 
Заслуженный участник


12/09/10
1547
Для таких последовательностей всегда можно найти рекуррентное соотношение а-ля Фибоначчи
(здесь нас интересуют только нечетные члены): $x_{2k+3}=ax_{2k+1}+bx_{2k-1}$ с целыми $a $ и $b$.
Сделать это можно несколькими способами, например, подбором по первым членам и дальнейшим доказательством по индукции. Если знаете про характеристические функции, то там делать совсем нечего.
После этого решение в одну строчку.

 Профиль  
                  
 
 Re: Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение25.07.2017, 19:28 
Заслуженный участник


12/07/07
4466
Cash, спасибо. Как я понял вариант решения.
Для нечетных $n=2k+1$ последовательность можно записать в виде $$y_{k} = (1+\sqrt 3)(4+2\sqrt 3)^k + (1- \sqrt 3)(4 - 2\sqrt 3)^k.$$ В правой части линейная комбинация базисных решений некоторого линейного однородного рекуррентного уравнения второго порядка с постоянными коэффициентами (РУ). Характеристическое уравнение этого РУ $$(r-r_1)(r-r_2)=0,$$ где $r_1=(4+2\sqrt 3)$, $ r_2=(4-2\sqrt 3)$. Следовательно, РУ и начальные условия такие:
$$y_{k+2} = 2^2(2y_{k+1} - y_k),$$ $$y_0 = 2^1, \qquad y_1 = 2^2 \left[(1+\sqrt 3)(2+\sqrt 3)^2 + (1-\sqrt 3)(2-\sqrt 3)^2 \right].$$Из РУ и начальных условий следует, что степень 2 в разложении $y_{k}$ не меньше $2^2$ умножить на степень $y_{k-2}$. Т.к. степень 2 в $y_0$ — первая, то степень двойки в $y_{k}$ не ниже $k+1$. Остаётся показать, что и не выше. Как-то так.

Но мне казалось, что было и другое решение.

 Профиль  
                  
 
 Re: Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение25.07.2017, 23:13 
Заслуженный участник


12/09/10
1547
Если $y_k=2^{k+1}(2m+1)$, а $y_{k+1}=2^{k+2}(2n+1)$, то $y_{k+2}=8y_{k+1}-4y_k=2^{k+3}\left[4(2n+1)-(2m+1)\right]$

Но что-то мы для ТС ничего не оставили.

 Профиль  
                  
 
 Re: Максимальная степень двойки floor ( (1+sqrt 3 )^n )
Сообщение26.07.2017, 00:38 
Заслуженный участник


12/07/07
4466
В таких простых примерах очень трудно что-то написать содержательное, не разобрав по существу пример, кроме как ссылки на книги. Детали CliniqueHappy сможет восстановить самостоятельно. Не будем ему в этом мешать. (Я там специально «туманил» последний шаг.)

В данном случае оба варианта решения практически одинаковы по сложности/удобству. Первый вариант вроде более очевиден и прост. А можно ли привести пример, когда второй вариант [c использованием рекуррентной последовательности] более удобен/полезен? (Я понимаю, что простота/удобство очень субъективны, но всё же интересно.) Может кому-то будет полезно/интересно (ТС в первую очередь); и я как найду время, поковыряюсь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group