Finding Formula for Recursive Relation

[winged anvil]

Need a closed-form formula for a_n. The problem and my work so far:

[winged anvil]

After the last line, I have no clue

[dark igloo]

ah.. I've done Abit of fiddling about the types of summati like that

U might want to take a look at Stirling's number

[winged anvil]

well, is my approach and the math for it correct in the first place?

This problem was chosen by my prof and given that he hasn't lectured on Stirling's number, I doubt it's required to solve the recursive relation

[dark igloo]

It looks correct

[winged anvil]

ok 😂

the series can't be manipulated into geometric/arithmetic sum(s)?

[spring forge]

it can't be right

you're describing
a(n) = 1a(n-1) +n2^n

[spring forge]

ok, I got it

I did it kind of brute forcey and didn't prove it but you can do the induction stuff

define b(n) = 2^n

define c(n) = a(n) / b(n) is quadratic and pretty easy to figure out

[iron dirge]

its possible to simplify that one even more

ive found that its actually mistaken , i'm not sure , but i'll show u my solution

[iron dirge]

my solution was an = 2^n x (a0 + n(n+1)/2 )

[dark igloo]

a(n) = 2^(n-1)(n^2+n+a_1)

[dark igloo]

Yeah if u set b(n) = a(n)/2^n,the question becomes
b(n) = b(n-1)+ n

[spring forge]

I figured this out a while ago. I didn't present the full answer because I wanted the questioner to think about it

[dark igloo]

It does if u manipulate it abit

[spring forge]

i see it but we're trying to get away from recursive

[dark igloo]

Dude,the equation is literally called a recurrence relation

[spring forge]

the question is asking for a closed form solution

[dark igloo]

Yeah,u can figure that from here...

U can do it by subtracting both sides by b(n-1) and then summing it

Creating a telescoping sum

[spring forge]

I already did days ago. You know I'm, not the original questioner right?

[dark igloo]

I know

[iron dirge]

how did you get that

[dark igloo]

.

[iron dirge]

lemme show you how i simplified it , i think its not necessary

@dark igloo

@spring forge how did you get ur result?

[spring forge]

I saw it was exponential so I divided by 2^n and the closed form was obvious

[iron dirge]

did you try and sibstitute ? because when i did the substituion into my closed formula it was correct

[dark igloo]

Yeah but u still need to proof that

$a(n) = 2^k a(n-k) + 2^n \sum_{i=1}^k n - i + 1$

(by induction,u can't just assume the pattern holds)

[last perch]

impract1cal

[dark igloo]

After u do that,set k = n and u get ur result

[iron dirge]

well yeah i have to use induction your right , but the explicit formula is true

yes

do you they want the explicit formula for some natural number k ?

or until 0

[dark igloo]

nah, but u can use that to get a(n)

[iron dirge]

yes

[dark igloo]

but if u dont want to do induction and still be formal about it, set b(n) = a(n)/2^n, then
b(n) = (2a(n - 1) + n2^n)/2^n
= 2a(n - 1)/2^n + n
= (2b(n - 1)2^(n - 1))/2^n + n
= b(n - 1) + n

[iron dirge]

$a(n) = 2^k ( a0 + \sum_{i = 1 }^n i $

[dark igloo]

b(n) - b(n - 1) = n

[iron dirge]

thats a good way to approach it

yes

[dark igloo]

$\sum_{k=1}^n (b(k) - b(k - 1)) = \sum_{k=1}^n k$

[last perch]

impract1cal

[dark igloo]

that telescopes

so yeah

[iron dirge]

oh ye this works really well , it didint seem right to me when i first look at it , but now it makes sense thanks

[dark igloo]

hahaha

anyways

b(n) - b(0) = 1/2n(n+1)

b(n) = b(0) + 1/2n(n+1)

which means a(n) = 2^n(b(0) + 1/2n(n+1))

note that b(0) = a(0)/2^0 = a(0)

[iron dirge]

oh yes , thats the closed form , thanks for your explanation

[dark igloo]

try proving this tho, it seems like a fun exercise anyway

proof that $a(n) = 2^k a(n-k) + 2^{n-1} k (2n + 1 - k)$

[last perch]

impract1cal

[iron dirge]

sure ill do it

induction on k? right

[dark igloo]

yeah

[iron dirge]

there is a small error

i think its in my proof

nt

not sure

-2K - K , it should be -2K + K

im not sure why

[winged anvil]

I did ended up getting it, thanks for the help