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 = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:
<tex>m_{h+1} - m_h = m_h - + m_{h-21}</tex>, <tex>m_{h+1} - m_h = F_(m_{h-2} +3} - F_m_{h-1} +2}1) </tex>, (по определению) <tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>, <tex>1 - (F_{h+2} - F_h = F_{h+1}) </tex>, (по индукционному переходу) <tex>F_{h+1} = F_{h+1}</tex>. (по определению чисел Фибоначчи)
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
