59
правок
Изменения
→Высота дерева
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.
Тогда <tex>m_{h+1} - m_h = m_h + m_{h-1} + 1 - (m_= F_{h-+2} + m_{h-1} + 1) </tex> (по определению) <tex> = F_{h+31} - 1 - (F_{h+2} - 1) </tex> (по индукционному переходу) <tex> = F_{h+3} - 1} </tex> (по определению чисел Фибоначчи) .
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
