a.請基于公式2ⁿ=2^n-1+2^n-1，設(shè)計(jì)一個遞歸算法。當(dāng)n是任意非負(fù)整數(shù)的時候，該算法能夠計(jì)算2n的值。
b.建立該算法所做的加法運(yùn)算次數(shù)的遞推關(guān)系并求解。
c.為該算法構(gòu)造一棵遞歸調(diào)用樹，然后計(jì)算它所做的遞歸調(diào)用次數(shù)。

考慮下列遞歸算法，該算法用來計(jì)算前n個立方的和：S（n）=13+23+…+n3。
算法S（n）
//輸入：正整數(shù)n 
//輸出：前n個立方的和
if n=1 return 1
else return S（n-1）+n*n*n
建立該算法的基本操作次數(shù)的遞推關(guān)系并求解。

解下列遞推關(guān)系（做a，b）

對下列斷言進(jìn)行證明：（如果是錯誤的，請舉例）
a. 如果t（n）∈O（g（n），則g（n）∈Ω（t（n））
b.α＞0時，Θ（αg（n））= Θ（g（n））