Solving Recurrence Relation Forward Substitution Explained

Описание: This video explains and shows step by step how to solve a recurrence relation or recurrence equation using forward substitution method that involves solving a finite mathematical series with application in computer science, algorithm and discrete math. The recurrence formula in this example states that next term of the sequence is equal to two times previous term plus two times the index of the next term. The index of the initial term of the progression is one and the initial term's value is six. Forward substitution is applied to find the formulas for the second term, third term and forth term of the sequence. A clear pattern is then observed in the formulas for those terms. The observed pattern is then extrapolated to write the formula for the general term (nth term) of the sequence. The resulting formula includes a finite series that needed to be solved. A clever and simple difference-of-terms technique is used to convert the series to an -easy-to-compute geometric series in order to find a closed-form formula for the finite series and therefore solve the recurrence relation by finding the mathematical formula that describes the general term (nth term) of the sequence as a function of the index n. The formula states that then nth term of the sequence (with index value n) is equal to 6*2^n - 2*n -4.