I am having serious problem with these problems

1)if T(n) has the property that T(0) is O(1) and T(n) <= T(n-1) + f(n), where f(n) is a function that consumes and returns a natural number which is O(n), then T(n) is O(n^2), but i need to prove this by induction on n, using the definition of O-notation, how can i do it?

For this problem i am guessing that i need to find a relation between You're given a relation between T(n), T(0) and f but i dont seem to find it.

2)This problem is in 2 parts, the first 1 is

a)

(define (mod-exp1 m e n) (cond [(zero? e) 1] [else (modulo (* (mod-exp1 m (- e 1) n) m) n)]))

*The code is in scheme if anyone interested; anyways it's a recursive function where cond is equal to if in other languages and (* a b c) = (a*b*c).

Assuming that m E{0,...,n-1}, let T_1(e) be the number of multiplications needed to compute (mod-exp1 m e n) on any legal input. Give an explicit formula for T_1(e).

For this i think it should take e numbers of multiplication or at least thats is what i deducted so it could be something like this??

T_1(e)= a + (T_1 e -1) where a is a positive constants and are some steps or should it be 1 because it's counting the number of multiplications??

(define (mod-exp2 m e n) (cond [(zero? e) 1] [(even? e) (modulo (mod-exp2 (sqr m) (quotient e 2) n) n)] [else (modulo (* (mod-exp2 (sqr m) (quotient e 2) n) m) n)]))

where (sqr m) = m^2

Let T_2(e) be the number of multiplications needed to compute (mod-exp2 m e n). Describe T_2(e) by a recurrence relation, indicating what the diffrent cases are. Give an estimate for T_2(e) in O-notation.

Hint:Assume that 2^(L-1) < e <2^L. What is the cost of the algorithm in terms of L? what is the relationship between L and n?

but im still in doubt on this one

Thanks for the help