If functions `f:{1,2,…,n} rarr {1995,1996}` satisfying f(1)+f(2)+…+f(1996)=odd integer are formed, the number of such functions can be

Options

A. `2^(n)`
B. `2^(n//2)`
C. `n^(2)`
D. `2^(n-1)`

Answer

To solve the problem of finding the number of functions \( f: \{1, 2, \ldots, n\} \to \{1995, 1996\} \) such that the sum \( f(1) + f(2) + \ldots + f(n) \) is an odd integer, we can follow these steps:

### Step 1: Understanding the Function Values
The function \( f \) can take values from the set \{1995, 1996\}. Notably, 1995 is an odd number and 1996 is an even number.

### Step 2: Determine the Sum's Parity
For the sum \( f(1) + f(2) + \ldots + f(n) \) to be odd, we need to consider how many times each value (1995 and 1996) is chosen. The sum will be odd if there is an odd number of odd values (1995) in the sum.

### Step 3: Count the Odd Values
Let \( k \) be the number of times we choose 1995. The remaining \( n - k \) values will be 1996. For the sum to be odd, \( k \) must be an odd integer.

### Step 4: Possible Values for \( k \)
The possible odd values for \( k \) range from 1 to \( n \) (if \( n \) is odd) or from 1 to \( n-1 \) (if \( n \) is even). Thus, \( k \) can take values: 1, 3, 5, ..., up to the largest odd number \( \leq n \).

### Step 5: Counting the Functions
For each valid odd \( k \), the number of ways to choose \( k \) positions from \( n \) is given by the binomial coefficient \( \binom{n}{k} \). Therefore, we need to sum these coefficients over all odd \( k \).

### Step 6: Using Binomial Coefficients
The sum of binomial coefficients for odd \( k \) can be expressed using the identity:
\[ \sum_{k \text{ odd}} \binom{n}{k} = 2^{n-1} \]
This is derived from the binomial expansion of \( (1 + 1)^n \) and \( (1 - 1)^n \).

### Step 7: Conclusion
Thus, the total number of functions \( f \) such that \( f(1) + f(2) + \ldots + f(n) \) is odd is given by:
\[ 2^{n-1} \]

### Final Answer
The number of such functions is \( 2^{n-1} \).