想请问substitution method的归纳法想法
此题 T(n)=T(3n/4)+T(n/5)+n+1
猜T(n)=O(n)，所以要证T(n)<=cn
解答假设T(m)<=cm,for all m<n
对n做强归纳法证明，应该是n<=m成立（此却是m<n？），然后用前面证n=m+1
不太理解此的强数归想法，若此用强数归不是应该用n<=m成立结果去证n=m+1吗？
课本证明（手机拍不清用打的）：林立宇算法讲义p13
T(n)=T(3n/4)+T(n/5)+n+1 <= c(3n/4)+c(n/5)+n+1 <=c(3n/4)+c(n/5)+n+n
=(c(19/20)+2)n <= cn 当c>=40,n>=1成立 所以T(n)=O(n)
另外这边的猜是用O，前面用Θ，是因为substitution只能证一边所以才写O？
感谢各位