[離散] 離散(3)

[PttFund (批踢踢基金只進不出)]

The number f(n) of steps required to solve the "chinese rings
puzzle" with n ring satisfies f(1) = 1 and

        f(n+1) = 2f(n)          if n is odd,
                 2f(n) + 1      if n is even.

Prove that f(n+2) = f(n+1) + 2f(n) + 1.  Hence or otherwise
find a formula for f(n) in term of n.


--
我好窮啊，我好缺批幣啊
，你有摳摳ㄋㄟ
可憐可憐我吧，施捨一點吧
請到(P)LAY-->(P)AY-->(0)GIVE-->PttFund-->吧

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.218.142
推 JGU:2^(n+1)/3 + (-1)^(n+1)/6 - 1/2
→ eggsu       :我也做出來了，謝謝JGU的答案讓我能把答案更化簡
→ eggsu       :本來我做出來的是
→ eggsu       :當 n 是奇數時，f(n) = 2^(n+1)/3 - 1/3
→ eggsu       :當 n 是偶數時，f(n) = 2^(n+1)/3 - 2/3
→ eggsu       :加強了對振盪數列的體會，感恩啊！