Resolve recurrence relation from function-CodePudding

The function Dots prints dots on screen:

Dots(n)
  if n==1 then
    Write(.)
  else
    for i=1 to n-1 do
      Dots(i)
    for i=1 to n do
      for j=1 to n do
        Write(.)

How many dots will be printed for n?

CodePudding user response：

The recurrence relation for counting number of dots is like.

if n > 1
    T(n) = T(1)   ...   T(n-1)   n ^ 2
else 
    T(n) = 1

You can write the below function to find the number of dots:

def Dots(n):
  if n==1:
    return 1
  else:
    dots = 0
    for i in range(1, n):
      dots  = Dots(i)
    for i in range(1, n   1):
      for j in range(1, n   1):
        dots  = 1
    return dots

for i in range(1, 6):
  print(i, "dots =", Dots(i))

OUTPUT

1 dots = 1
2 dots = 5
3 dots = 15
4 dots = 37
5 dots = 83

CodePudding user response：

We can rewrite the code as a function that computes the number of dots:

D(n)
  if n==1 then
    return 1
  else
    Count= 0
    for i=1 to n-1 do
      Count = D(i)
    for i=1 to n do
      for j=1 to n do
        Count  
    return Count

This corresponds to the recurrence

D(1) = 1
D(n) = Σ(i= 1, n-1) D(i)   n²

We can rework as follows to bring it in a more familiar form:

D(n) = D(n-1)   Σ(i= 1, n-2) D(i)   n² = 2D(n-1)   2n - 1.

The rest is routine work. Multiplying by 2^(-n),

2^(-n)D(n) = 2^(-(n-1))D(n-1)   2^(-n)(2n - 1)

and you obtain 2^(-n)D(n) by summation.