When trying to work out a rule for a sequence with a third difference of 1 what do i do?

[hybrid echo]

so for second difference of 1

you would multiply 1 by that n^2/2

and youd get the rule for that sequence and find nth term and what not

but what about third differences?

what do you do then

so if i had a sequence with a third difference of 1 what would i do

[gloomy cairn]

I don't understand the point

What are you trying to do

[hybrid echo]

i have a sequence, and its got a third difference of 1

has a third difference of 1

so waht do i do next, like how do i get the rule for this sequence

[gloomy cairn]

1,4,10,20,35,56 is the sequence of triangular numbers

Which are given by
$T_n = \frac{n(n+1)(n+2)}{6}$

[loud charm]

Daddy_314

[gloomy cairn]

So the first difference is
$T_{n+1} - T_n$

[loud charm]

Daddy_314

[hybrid echo]

ok but what if i didnt know that, how would i figure out, the sequence if third difference is a 1 lol

of a sequence

[gloomy cairn]

Two distinct sequences can have the same difference sequence

Like 2 , 4 , 6 , 8

And 1,3,5,7...

You cant guess back the original sequence only using the differences

[hybrid echo]

hmmmm

so what if i didnt know

that it was a triangle number sequence

[gloomy cairn]

Well you do need some definition of your sequence

To begin with

You cant start computing differences of terms you dont even know how to compute...

If the sequence is obvious or geometric/arithemtic you can always express it in terms of n, and then find the differences successively

In terms of n

Notice that "the difference sequence" is similar to the derivative of a function

$\frac{f(x)-f(y)}{x-y}$
And
$ \frac{u_{n+1}-u_n}{(n+1)-n}$
Rings a bell ?

[loud charm]

Daddy_314

[hybrid echo]

hmmm first one sort of i think its comparing like two functions right, second not so much

how would u solve to find the nth term in that sequence without knowing it was a triangle number sequence? how would you do it personally

[gloomy cairn]

Well

This is exactly why you should take the textbook you found that exercise in and burn it

Because when I give you a sequence like so:

1 , 2 , 3, 4....

It may be obvious that i mean the sequence $u_n = n$

[loud charm]

Daddy_314

[gloomy cairn]

But it could be 1,2,3,4,927,62829

For all you know

[hybrid echo]

hmmm i see what u mena

[gloomy cairn]

So as long as I do not tell you exactly how I am generating a sequence

In a unique way

There is no point doing any "computations"

They will be worth shit

If you do know how I am defining a sequence in terms of n (or Un+1 and Un etc) then you have a chance at finding the differences

[hybrid echo]

hmm i see, so its good to first identify what sequence type it is first? so like linear, etc

exponatiaonal

and thne from there you can find its rule

and what not?

and use it to get nth term?

[gloomy cairn]

We dont identify it

They must give it

Yes

They must tell you exactly the full sequence

[hybrid echo]

hmmm i see

[gloomy cairn]

They cant just tell you
1,4,7,9

This is bullshit

It can be anything after that

Burn that book

Immediately

[hybrid echo]

alrighty, but for my case it goes on infinitely like that,

so i think for my case it can be safe to assume it goes in that tirangle number pattern

[gloomy cairn]

Again

[hybrid echo]

coz basically this sequence represents the number of times some (loop in a program runs)

[gloomy cairn]

Oh ! Now we are talking

[hybrid echo]

1,4,10,20,35,56

[gloomy cairn]

This means there is context

[hybrid echo]

but imagine theres 2 nested loops

for loops

[gloomy cairn]

Yeah

[hybrid echo]

1st nested loop, is linear

[gloomy cairn]

Triangular numbers are very useful

Because they come from the sequence of sum of consecutive integers

[hybrid echo]

so first for loop, runs 3 times, second loop would run 6 times and third one would run 10 times

and this 10 times one is traignle number pattern

[gloomy cairn]

When the first loop goes from k = 1 to n
And j the second loop goes from k to n to

[hybrid echo]

hmm no, second loop goes from 1 to k

third loop goes from 1 to j

first loop goes from 1 to n

so if n = 5

first loop = 1,2,3,4,5

second loop: would have its k as 1, 2, 3, 4, 5

so if its 1, it would run once, 2 means it would run 1 and 2, so 3 times in total

so 1, 3, 6, 10 (in terms of how many times it runs)

[gloomy cairn]

This almost the same thing

But yes

[gloomy cairn]

You are just taking the lower half of the triangle

[hybrid echo]

mhm

[gloomy cairn]

Triangular numbers are symmetric

I took the upper half

But

This is almost the same

i varies between 1 and n

If j varied between 1 and n also, you would have

(1;1)
(1;2)
(1;3)
(1;4)
(1;5)
(2;1)
(2;2)
(2;3)
...

25 times

But since we dont want to take "equal" couples (for example (2;1) and (1;2) we constrain i < j (or i > j)

This way we throw the garbage out

So we get
For i = 1, 5 possible j and so 5 couples
For i = 2 , 4 possible j and so 4 couples
For i = 3, 3 possible j
....
So you have 5+4+3+2+1=(5 * 6)/2 couples
Instead of (5 * 5)

[hybrid echo]

mhmm i see

well, if it was nested loops and it would be from i,k,j to n

like i ---> n

and k ---> n

and j ----> n

then all of those would be linear

[gloomy cairn]

There is nothing linear

In the entire exercise

[hybrid echo]

how come, i ----> n would be linear

if it goes from 1 to 5

[gloomy cairn]

If you really insist yes

[hybrid echo]

for example

[gloomy cairn]

But

This is not the hard part

At all

Everyone knows i increments from 1 to n

In steps of 1

Thats like saying the sky is above us

[hybrid echo]

yea and so if u got 3 nested of these

it would just be n ^ 3

[gloomy cairn]

Yes

[hybrid echo]

but becasue in this problem

the next time it loops, it uses the i

and then the j or k

that means only first is linear

[gloomy cairn]

Yes this is exactly the benefit

The second loop is also linear

Its the nesting that makes it

Not linear

In complexity

Also the word " linear" alone is meaningless

Running time/memory/ complexity is linear, quadratic etc

Triangular numbers n(n+1)/2 also grow almost like n^2 bt the way

[hybrid echo]

almost? hmmm but not exact

right

[gloomy cairn]

Asymptotically they are both quadratic

[hybrid echo]

hmmm u mean they are close enough to just be called quadratic? lol

[gloomy cairn]

Anything proportional to n^2 is quadratic

n^2/2 is also a parabola

Its just a bit nicer

But its not a huge improvement

[hybrid echo]

ah n^2/2

would just be n^2, we can ignore the /2

[gloomy cairn]

(I was talking about two nested loops)

[hybrid echo]

it dont matter much

[gloomy cairn]

No we cant...

Well depends what we are aiming to do

[hybrid echo]

oh nvm

[gloomy cairn]

In limits you cannot ignore

Factors affecting the largest variables

You dont say ok everything is approximately 1

If your running times are very smooth in your code

And you have a bottleneck at n^2/2

Etc

[hybrid echo]

hmm alr

alr well thanks ima close the thread now, thanks for helping out

.close

[golden holly]

Solved

Post marked as solved by @hybrid echo.

Use .unsolved if this was a mistake.