Мундарижа Кириш

А(1)=А(0)=0.

Агар йиғиндига диққат билан қарасак, унда биринчи қўшилувчи аргументи 0 дан то N-1 қийматлардан ўтади, иккинчи қўшилувчи аргументи эса— худди шундай қиймат, фақат камайиш тартибида.

Бу шуни кўрсатадики, ҳар бир А(i) қўшилувчилардан бири йиғиндида икки марта учрайди ва формулани соддалаштириш мумкин:

учун

А(1) =А(0) = 0.

Бундай шаклдаги муносабат жуда мураккаб кўринади. Бу мураккабликни икки усул билан бартараф этиш мумкин. Биринчи усул ўзининг тайёргарлигидан фойдаланиб, тўғри формулани қидириб топиш ва кейин у рекуррент муносабатни қаноатлантиришини исботлаш керак. Иккинчи усул икки формулага биргаликда қарашни таъкидлайди: A(N) ва A(N - 1) лар учун. Бу икки ифода айрим аъзолари билан фарқ қилади.

Касрлардан қутулиш учун A(N)·N ва A(N–1)·(N–1) ларни ҳисоблаймиз.

Ҳосил қиламиз

Иккинчи тенгликдан учинчи тенгликни айирамиз ва айрим соддалаштиришлар бажариб, ҳосил қиламиз

Охирги тенгликнинг ҳар иккала қисмига A(N–1) • (N–1) ни қўшилиши қуйидагни беради

бундан якуний рекуррент муносабатни келтириб чиқарамиз

A(1) = А(0) = 0.

Уни ечиш қийин эмас ва етарлича таҳлил тенгликни беради. Шундай қилиб тез саралаш алгоритмининг ўртача қийинлиги га тенг.