CODEWITHSUNDEEP
discrete-mathematicsrecurrence
GonePhisin
GonePhisin

Reputation: 45

Having a hard time understanding recurrence relation solutions

So the question is A0 = 4, A(n)=A(n-1) - n So far what I have is A(1)=3, A(2)=1, A(3)=-2, A(4)=-6. I understand how to get those numbers and I could infinitely go up if I wanted to. But I'm having a hard time understanding the logic to finding the solution.

Thanks guys!

Upvotes: 2

Views: 296

Answers (2)

Patrick87
Patrick87

Reputation: 28292

A(n) = A(n - 1) - n
A(0) = 4

n    A(n)
0    4
1    A(0) - 1 = 4 - 1
2    A(1) - 2 = 4 - 1 - 2
3    A(2) - 3 = 4 - 1 - 2 - 3
...
k    A(k-1) - 3 = 4 - 1 - 2 - ... - k
                = 4 - (1 + 2 + ... + k)
                = 4 - [(1+k) + (2+k-1) + ... + (k/2 + k/2+1)], if k is even
                  4 - [(1+k) + (2+k-1) + ... + (k/2 + 0.5)], if k is odd
                = 4 - [(k+1) + (k+1) + ... + (k+1)], if k is even
                  4 - [(k+1) + (k+1) + ... + (k+1)/2], if k is odd
                = 4 - (k/2)(k+1), if k is even
                  4 - (k/2-1)(k+1) + (k+1)/2, if k is odd
                = 4 - (k/2)(k+1), if k is even
                  4 - (k/2)(k+1), if k is odd
                = 4 - (k/2)(k+1), for all k

Upvotes: 0

Alexander Larios
Alexander Larios

Reputation: 62

What you have here is a negative version of the Arithmetic Sequence. I use when looking at the relation is to try to understand the relationship between the outputs A(1)=3, A(2)=1, A(3)=-2, A(4)=-6 .... so I look at A(1)=3 and A(2)=1 and A(3) =-2... I ask myself what happened in each step to get to the next. for A(2) n=2, I had to take A(1)=3 and subtract the value of n = 2. As you know that pattern holds up as far as you want to go. So now we have this pattern to get the value of the nth element of a sequence A(n) in relation to the previous value A(n-1), to solve the recurrence relation we have to look at the big picture and have a bit of intuition on the structure. EDIT:

 - given n=0 A(0)= 4
 - n=1 A(1)=A(0)-1 = 4-1
 - n=2 A(2)=(4-1)-2 = 4 -(1-2) 
 - n=3 A(3)=((4-1)-2)-3 = 4 -(1-2-3)
 - n=4 A(4)=(((4-1)-2)-3)-4 = 4-(1-2-3-4)

so we can see that 4 is a constant that we always subtract the Σ of -1 through -n from. This is where a little bit of memorization comes into play. We know that the Arithmetic sequence looks like Σ of 1 through n = to (n(n+1))/2 so we can guess that if we throw a negative sign in here that we will have the negative version. Lets try 4-((n(n+1)/2). This is the answer. I wish it was more intuitive to get to the Arithmetic sequence but you will want to memorize that and the geometric sequence as they come up a lot.

Let me know if you have more questions.

Upvotes: 1

Related Questions