Question

Solve the recurrence relation . x(n)=x(n/3)+n for n>1 ,x(1)=1

Answer 1

The solution to the recurrence relation is $x(n) = \frac 12(3n - 1)$

How to solve the relation?

The relation is given as:

x(n) = x(n/3) + n for n > 1

x(1) = 1

Calculate x(3)

x(3) = x(3/3) + 3

This gives

x(3) = x(1) + 3

x(3) = 1 + 3 = 4

Calculate x(9)

x(9) = x(9/3) + 9

This gives

x(9) = x(3) + 9

x(9) = 4 + 9 = 13

So, we have:

x(1) = 1

x(3) = 4

x(9) = 13

The above sequence forms an arithmetic sequence.

An arithmetic sequence is represented as:

x(n) = x(1) + (n - 1) * d

Substitute 9 for n

x(9) = x(1) + (9 - 1) * d

Substitute 13 for x(9) and 1 for x(1)

13 = 1 + (9 - 1) * d

This gives

12 = 8d

Divide by 8

d = 1.5

Substitute d = 1.5 in x(n) = x(1) + (n - 1) * d

x(n) = x(1) + (n - 1) * 1.5

Substitute x(1) = 1

x(n) = 1 + (n - 1) * 1.5

Expand

x(n) = 1 + 1.5n - 1.5

Evaluate the like terms

x(n) = 1.5n - 0.5

Express as fraction

x(n) = 3n/2 - 1/2

Factor out 1/2

$x(n) = \frac 12(3n - 1)$

Hence, the solution to the recurrence relation is $x(n) = \frac 12(3n - 1)$

Read more about recurrence relation at:

brainly.com/question/4082048

#SPJ1