# Proof by induction: finding a closed form solution

I need to prove the following by induction:

Let $p_{1}$, $p_{2}$, $p_{3}$, $...$, $p_{m}$ be distinct primes.

Let $a_{1}$, $a_{2}$, $a_{3}$, $...$, $a_{m}$ be positive integers.

Suppose the following...

\begin{equation} N = (p_{1})^{a_{1}} * (p_{2})^{a_{2}} * (p_{3})^{a_{3}} * ... * (p_{m})^{a_{m}} \end{equation}

How many divisors does $N$ have?

I thought about it, and concluded that given that we're working with distinct primes, the following is true:

\begin{equation} \# \hspace{.2cm}of\hspace{.2cm} Divisors\hspace{.2cm} of\hspace{.2cm} N = (a_{1} + 1) + (a_{2} + 1) + (a_{3} + 1) + ... + (a_{m} + 1) \end{equation}

The problem is that I haven't done a proof by induction in a long time, and I think that I remember how to do it once I have the closed form, but I'm not sure how to turn the above equation into a closed form solution.

I vaguely remember using summation notation to get closed form solutions, so I attempted to turn this into a summation as well (which I may have done incorrectly):

\begin{equation} \# \hspace{.2cm}of\hspace{.2cm} Divisors\hspace{.2cm} of\hspace{.2cm} N = (\sum_{i = 1}^{m} a_{i}) + m \end{equation}

I also know that the closed form of $(\sum_{i = 1}^{n} i)$ is ${[n(n+1)]}\div{2}$, but I'm not sure if the index numbers $1 - n$ have to be consecutive in order for that to work, and they aren't necessarily consecutive in this particular case.

Any help would be hugely appreciated.

## 1 Answer

Pretty sure the answer is actually:

$\Pi_{i=1}^{m} (a_m + 1)$

i.e., product instead of sum.

For example, if m=2 and the p values are 2 and 3 and the a values are 2 and 2, you get N=36, which has 9 divisors (3 times 3), not 6 divisors (3 plus 3).

These divisors are: 1, 2, 4, 3, 6, 12, 9, 18, 36

• You're right, my mistake. Thank you! How do you find the closed form for product notation..? – BabaSvoloch Apr 27 '17 at 21:04
• This is already in closed form... I'll let you work out the proof... wouldn't want to have all the fun. – Jed Apr 27 '17 at 21:25