1. Data la seguente proposizione dimostrabile per induzione

    $$ 1+2+...+n=\frac{n(n+1)}{2}\space \space \space \forall n\ge 1 $$

Indicare quale tra le seguenti espressioni rappresenta l’utilizzo dell’ipotesi induttiva nella dimostrazione del passo induttivo $p(n)\Rarr p(n+1)$

  1. $1=\frac {1(1+1)}{2}$
  2. $\sum^{n+1}{1=1}i=\sum^{n}{i=1}i+n+1$
  3. $\sum^{n+1}_{i=1}i=\frac{(n+1)(n+2)}{2}$
  4. $\sum^{n}_{i=1}i+n+1=\frac{n(n+1)}{2}+n+1$

  1. Date le seguenti funzioni

    $$ f(n)=n+log_2(n^4),\space \space \space g(n)=\frac 12n^2 $$

Indicare il minimo valore intero che può essere assegnato a $c$ per dimostrare $f(n)=O(g(n))$ ponendo $n_0=1$

  1. Dato il seguente insieme non ordinato di funzioni in $n$

$$ \{ \frac 1n,n^n,log^2n+logn,-10,n\sqrt n,\sqrt{logn},2^{n+2} $$

Assegnare ciascuna funzione ad un indice diverso $i\in \{1,...,7\}$ affinché sia valido il seguente ordinamento:

$$ f_1(n)\le f_2(n)\le ...\le f_7(n) $$

dove $f_i(n)$ è la funzione assegnata all’indice $i$, e $\le$ è la relazione d’ordine basata sul tasso di crescita delle funzioni

  1. (a) Risolvere la seguente relazione di ricorrenza utilizzando il metodo iterativo o il metodo dell’albero di ricorsione per ottenere un’espressione equivalente in $n$ (Esempio: $\frac 73 nlognn+5n$)