Passo 1. P(e) è la somma di vari addendi: il numero C^e₁ dei sottinsiemi di S_e formati da un solo elemento, più il numero C^e₂ dei sottinsiemi di S_e formati da 2 elementi, e così via, fino al numero C^e_e-1 dei sottinsiemi formati da e - 1 elementi ed a C^e_e, che è uguale a 1, perchè S_e ha un solo sottinsieme di e elementi, cioè S_e stesso. In più c'è un altro addendo C^e₀ uguale a 1, che corrisponde all'unico insieme con 0 elementi, ossia l'insieme vuoto. Dunque

Osservate che P(e) è maggiore di 2 del numero che avete indicato con p nella vostra lettera; in altre parole P(e) = p + 2.

Passo 2. Calcoliamo ora gli addendi C^e_k. Innanzitutto come abbiamo già osservato C^e₀=C^e_e=1. Poi è chiaro che C^e₁ = e, ci sono esattamente e sottinsiemi di un elemento. Quanti sono i sottinsiemi di 2 elementi? Per costruire un tale sottinsieme posso scegliere un primo elemento in S_e in e modi diversi, poi per il secondo ho e - 1 scelte possibili, quindi in tutto ho e(e - 1) scelte. Però così uno stesso sottinsieme lo ottengo due volte, e dunque per trovare C^e₂ devo dividere per due: C^e₂=e(e - 1)/2. Ora calcoliamo C^e₃: per costruire un sottinsieme di 3 elementi ho e scelte per il primo elemento, e - 1 per il secondo ed e - 2 per il terzo, in tutto e(e - 1)(e - 2). Poi però per trovare C^e₃ devo dividere per il numero di modi in cui posso ordinare questi tre elementi, cerchiamo di capire quanti sono. Se i tre elementi sono i numeri 1,2,3 i modi possibili di ordinarli sono:

Il denominatore rappresenta il numero di modi in cui si possono disporre in ordine k elementi: il primo si può scegliere in k modi, il secondo in k - 1 modi, e così via.

Passo 3. Ora dobbiamo fare una piccola digressione e far entrare in gioco il triangolo di Tartaglia (o di Pascal). Supponiamo di avere due numeri a e b e la loro somma a + b: come si possono calcolare le potenze di questa somma cioè (a+b)ⁿ? Facciamo i conti nei primi casi:

In generale lo sviluppo di (a+b)ⁿ si otterrà moltiplicando ogni termine dello sviluppo di (a+b)^n-1, ottenuto precedentemente, per a e poi per b e addizionando. Si può visualizzare questa situazione nel seguente schema:

I coefficienti dei monomi che compaiono in ciascuna riga possono essere inseriti in un triangolo, detto di Tartaglia, cominciando dai coefficienti 1,1 di a + b, in modo che ogni numero nel triangolo sia la somma dei due numeri che lo precedono e lo seguono nella riga precedente:

Possiamo ora osservare che nella e-sima riga del triangolo di Tartaglia i numeri che compaiono sono proprio i coefficienti che abbiamo introdotto prima:

Abbiamo quindi ottenuto la regola:

che vale per ogni scelta di numeri a e b.

Passo 4. A noi interessa in particolare il caso a = b = 1. Infatti sostituendo 1 al posto sia di a che di b otteniamo l'uguaglianza che volevamo: (1+1)^e = 2^e = C^e₀+ C^e₁+ C^e₂+ ...+ C^e_e-1+C^e_e.

A questo punto possiamo provare a controllare se la regola che avete trovato è vera sempre, qualunque sia il numero e. La vostra regola, usando i nuovi simboli, si può riscrivere così:

e cioè

è proprio vera!

La formula che abbiamo trovato si sarebbe potuta trovare anche a partire da questa vostra osservazione, usando un procedimento detto per induzione, ma questo discorso per voi è ancora un po' troppo difficile.

La seconda osservazione che avete fatto si può esprimere dicendo che P(e)-2-(P(e-1)-2) è una potenza di 2, e questo è anche vero perchè basta osservare che 2^e-2^e-1=2^e-1.

Per scrivere questa risposta ho consultato il classico libro di Courant e Robbins, Che cos'è la matematica?, edito da Boringhieri. Per ulteriori spunti per il vostro insegnante, in particolare sul principio d'induzione, suggerisco il libro di Childs: Algebra. Un'introduzione concreta, ETS Editrice.