Recursive function

Algebra Level 4

n Δ m = { 1 n = m ( n 1 ) Δ m + n Δ ( m + 1 ) n > m 0 otherwise n\Delta m= \left\{ \begin{array}{ll} 1 & n=m \\ (n-1)\Delta m+n\Delta (m+1) & n>m \\ 0 & \text{ otherwise} \\ \end{array} \right.

We define the Δ \Delta operator when applied to two positive integers m , n m,n as shown above. What is the value of 32 Δ 11 32\Delta11 ?


The answer is 2097152.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

We claim that ( m + k ) Δ m = 2 k (m+k) \Delta m = 2^k for all k k and prove it by induction as follows:

1) When k = 1 k = 1 ,

( m + 1 ) Δ m = m Δ m + ( m + 1 ) Δ ( m + 1 ) = 1 + 1 = 2 1 \begin{aligned} \quad \quad (m+1) \Delta m & = m \Delta m + (m+1) \Delta (m+1) \\ & = 1 + 1 = 2^1 \end{aligned} .

\quad Therefore, the claim is true for k = 1 k = 1 .

2) Assuming the claim is true for k k , then

( m + k + 1 ) Δ m = ( m + k ) Δ m + ( m + k + 1 ) Δ ( m + 1 ) = 2 k + 2 k = 2 k + 1 \begin{aligned} \quad \quad (m+k+1) \Delta m & = (m+k) \Delta m + (m+k+1) \Delta (m+1) \\ & = 2^k + 2^k = 2^{k+1} \end{aligned} .

\quad The claim is also true for k + 1 k + 1 . Therefore, the claim is true for all k k .

Hence, 32 Δ 11 = ( 11 + 21 ) Δ 11 = 2 21 = 2097152 32 \Delta 11 = (11+21) \Delta 11 = 2^{21} = \boxed{2097152}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...