したがって、上述の漸化式からformula_40となり、この2番目の等号は帰納仮説によるものである。